POJ 3294 Life Forms（广义后缀自动机）

给定\(n\)个串，求在一半以上的串中出现过的最长公共子串

对\(n\)个串建广义后缀自动机，用树状数组统计\(parent\)树上每个节点子树包含的串的个数，之后遍历一遍求出最长公共子串长度，并标记相应节点，之后根据长度和标记在\(DAG\)上\(dfs\)即可

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int Maxn=200010;
vectorg[Maxn];
struct Q{
    int id,l,r;
}ask[Maxn];
int n;
struct Suffix_Automata{
    int maxlen[Maxn], trans[Maxn][26], link[Maxn], Size;
    vectorsz[Maxn];
    void clr(int x){
        maxlen[x]=link[x]=0;
        memset(trans[x],0,sizeof(trans[x]));
        sz[x].clear();
    }
	void init(){
        Size=1;
        clr(1);
    }
    inline int insert(int ch, int last,int id){
        if (trans[last][ch]){
            int p = last, x = trans[p][ch];
            if (maxlen[p] + 1 == maxlen[x]) {sz[x].push_back(id);return x;}
            else{
                int y = ++Size;
                clr(y);
                maxlen[y] = maxlen[p] + 1;
                for (int i = 0; i < 26; ++i)
                    trans[y][i] = trans[x][i];
                while (p && trans[p][ch] == x)
                    trans[p][ch] = y, p = link[p];
                link[y] = link[x], link[x] = y;
                sz[y].push_back(id);
                return y;
            }
        }
        int z = ++Size, p = last;
        clr(z);
        sz[z].push_back(id);
        maxlen[z] = maxlen[last] + 1;
        while (p && !trans[p][ch])
            trans[p][ch] = z, p = link[p];
        if (!p) link[z] = 1;
        else{
            int x = trans[p][ch];
            if (maxlen[p] + 1 == maxlen[x]) link[z] = x;
            else{
                int y = ++Size;
                clr(y);
                maxlen[y] = maxlen[p] + 1;
                for (int i = 0; i < 26; ++i)
                    trans[y][i] = trans[x][i];
                while (p && trans[p][ch] == x)
                    trans[p][ch] = y, p = link[p];
                link[y] = link[x], link[z] = link[x] = y;
            }
        }
        return z;
    }
    int pre[Maxn],c[Maxn],vis[Maxn];
    void solve_init(){
        for(int i=0;i<=Size+1;i++)g[i].clear(),pre[i]=c[i]=vis[i]=0;
        for(int i=2;i<=Size;i++)g[link[i]].push_back(i);
    }
    int in[Maxn],out[Maxn],num[Maxn],tim;
    void getdfn(int x,int fa){
        in[x]=++tim;
        num[tim]=x;
        for(int i=0;in/2){
                mx=max(mx,maxlen[i]);
            }
        }
        for(int i=2;i<=Size;i++){
            if(ans[i]>n/2&&maxlen[i]==mx){
                vis[i]=1;
            }
        }
        if(mx==0)puts("?");
        else dfs(1,0);
        puts("");
    }
}sam;
char s[Maxn];
int main(){
    while(scanf("%d",&n)&&n){
        sam.init();
        for(int i=0;i