后缀自动机
<pre><code class="language-cpp">#include <iostream>
#include <map>
using namespace std;
const int maxn = 1e6+5;
struct state{
int maxlen;
map<char, int> trans;
int link;
};
state suf_st[2*maxn];
int now, last;
void suf_init(){
now = last = 0;
suf_st[0].maxlen = 0;
suf_st[0].link = -1;
return;
}
void suf_push(char c){
int cur = now++;
suf_st[cur].maxlen = suf_st[last].maxlen + 1;
int p;
for(p = last; p != -1 & suf_st[p].trans[c]; p = suf_st[p].link){
suf_st[p].trans[c] = cur;
}
if(p == -1) suf_st[cur].link = 0;
else{
int q = suf_st[p].trans[c];
if(suf_st[p].maxlen + 1 == suf_st[q].maxlen) suf_st[cur].link = q;
else{
int clone = now++;
suf_st[clone].maxlen = suf_st[p].maxlen + 1;
suf_st[clone].trans = suf_st[q].trans;
suf_st[clone].link = suf_st[q].link;
for(; p != -1 && suf_st[p].trans[c] == q; p = suf_st[p].link){
suf_st[p].trans[c] = clone;
}
suf_st[q].link = suf_st[cur].link = clone;
}
}
last = cur;
}
</code></pre>