后缀自动机

#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;
}