题意：

求出现次数大于$\frac{n}{2}$的所有最长子串

题解：

之前用后缀数组+二分写过一次，现在试了下广义SAM，代码量确实少了不少
理解也很简单，加字符的时候记录出现的位置，传递一下即可。

AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 2e5+50;
char s[1005],ss[1005];
int last,tot,n,ans;
int nxt[MAXN][26],fa[MAXN],len[MAXN],cnt[MAXN],vis[MAXN];
inline void Init(){
    for(int i=0;i<=tot;i++){
        fa[i]=len[i]=cnt[i]=vis[i]=0;
        for(int j=0;j<26;j++) nxt[i][j]=0;
    }
    last=tot=1;
}
inline void Insert(int x,int k){
    int p=last,np=++tot;
    last=np;len[np]=len[p]+1;
    for(;p&&!nxt[p][x];p=fa[p]) nxt[p][x]=np;
    if(!p) fa[np]=1;
    else{
        int q=nxt[p][x];
        if(len[p]+1==len[q]) fa[np]=q;
        else{
            int nq=++tot;
            len[nq]=len[p]+1;
            memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
            fa[nq]=fa[q]; fa[q]=fa[np]=nq;
            vis[nq]=vis[q]; cnt[nq]=cnt[q];
            for(;p&&nxt[p][x]==q;p=fa[p]) nxt[p][x]=nq;
        }
    }
    while(np && vis[np]!=k) vis[np]=k,cnt[np]++,np=fa[np];
}
void dfs(int u,int l){
    if(l>ans || l!=len[u]) return;
    if(len[u]==ans && cnt[u]>n/2) { cout<<ss<<endl;return; }
    for(int i=0;i<26;i++){
        if(nxt[u][i]){
            ss[l]='a'+i;
            dfs(nxt[u][i],l+1);
            ss[l]=0;
        }
    }
}
int main(){
    while(~scanf("%d",&n) && n){
        Init();
        for(int i=1;i<=n;i++){
            scanf("%s",s); last=1;
            int ls=strlen(s);
            for(int j=0;j<ls;j++) Insert(s[j]-'a',i);
        }
        ans=0;
        for(int i=1;i<=tot;i++)
            if(cnt[i]>n/2 && len[i]>ans)
                ans=len[i];
        if(ans) dfs(1,0); else puts("?");
        puts("");
    }
    return 0;
}