后缀自动机专题

https://www.cnblogs.com/--560/p/5457023.html

SPOJ Longest Common Substring

求两串的最长公共子串

#include<bits/stdc++.h>
using namespace std;
const int MAX=2e6;
const int INF=0x3f3f3f3f;
struct Tire
{
    static const int MAXN=26;
    int nxt[MAX][MAXN],f[MAX],L[MAX],last,tot;
    void init()
    {
        last=tot=0;
        memset(nxt[0],-1,sizeof(nxt[0]));
        f[0]=-1;L[0]=0;
    }
    void add(int x)
    {
        int p=last,np=++tot;
        L[np]=L[p]+1;
        memset(nxt[np],-1,sizeof(nxt[np]));
        while(~p&&nxt[p][x]==-1) nxt[p][x]=np,p=f[p];
        if(p==-1) f[np]=0;
        else
        {
            int q=nxt[p][x];
            if(L[q]!=L[p]+1)
            {
                int nq=++tot;
                L[nq]=L[p]+1;
                memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
                f[nq]=f[q];
                f[q]=f[np]=nq;
                while(~p&&nxt[p][x]==q) nxt[p][x]=nq,p=f[p];
            }
            else f[np]=q;
        }
        last=np;
    }
    int find(char *s)
    {
        int len=strlen(s);
        int res=0,tmp=0,u=0;
        for(int i=0;i<len;++i)
        {
            int x=s[i]-'a';
            if(~nxt[u][x]) ++tmp,u=nxt[u][x];
            else
            {
                while(~u&&nxt[u][x]==-1) u=f[u];
                if(~u) tmp=L[u]+1,u=nxt[u][x];
                else tmp=0,u=0;
            }
            res=max(res,tmp);
        }
        return res;
    }
}SAM;
char s[MAX];
int main()
{
    while(~scanf("%s",s))
    {
        SAM.init();
        int len=strlen(s);
        for(int i=0;i<len;++i) SAM.add(s[i]-'a');
        scanf("%s",s);
        printf("%d\n",SAM.find(s));
    }
    return 0;
}

SPOJ Longest Common Substring II

多串最长公共公共子串

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
const int INF=0x3f3f3f3f;
struct Tire
{
    static const int MAXN=26;
    int nxt[MAX][MAXN],f[MAX],L[MAX],last,tot;
    int Min[MAX],Max[MAX];
    void init()
    {
        last=tot=0;
        memset(nxt[0],-1,sizeof(nxt[0]));
        f[0]=-1;L[0]=0;
        Min[0]=Max[0]=0;
    }
    void add(int x)
    {
        int p=last,np=++tot;
        L[np]=L[p]+1;
        memset(nxt[np],-1,sizeof(nxt[np]));
        Min[np]=L[np];
        while(~p&&nxt[p][x]==-1) nxt[p][x]=np,p=f[p];
        if(p==-1) f[np]=0;
        else
        {
            int q=nxt[p][x];
            if(L[q]!=L[p]+1)
            {
                int nq=++tot;
                L[nq]=L[p]+1;
                memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
                Min[nq]=L[nq];
                f[nq]=f[q];
                f[q]=f[np]=nq;
                while(~p&&nxt[p][x]==q) nxt[p][x]=nq,p=f[p];
            }
            else f[np]=q;
        }
        last=np;
    }
    void find(char *s)
    {
        int len=strlen(s);
        int u=0,tmp=0;
        for(int i=0;i<=tot;++i) Max[i]=0;
        for(int i=0;i<len;++i)
        {
            int x=s[i]-'a';
            if(~nxt[u][x]) ++tmp,u=nxt[u][x];
            else
            {
                while(~u&&nxt[u][x]==-1) u=f[u];
                if(~u) tmp=L[u]+1,u=nxt[u][x];
                else tmp=0,u=0;
            }
            Max[u]=max(Max[u],tmp);
        }
        for(int i=tot;i>=1;--i) Max[f[i]]=max(Max[f[i]],Max[i]);
        for(int i=0;i<=tot;++i) Min[i]=min(Min[i],Max[i]);
    }
    int cal()
    {
        int res=0;
        for(int i=0;i<=tot;++i) res=max(res,Min[i]);
        return res;
    }
}SAM;
char s[MAX];
int main()
{
    SAM.init();
    scanf("%s",s);
    int len=strlen(s);
    for(int i=0;i<len;++i) SAM.add(s[i]-'a');
    while(~scanf("%s",s)) SAM.find(s);
    printf("%d\n",SAM.cal());
    return 0;
}

SPOJ Substrings

求一个串长度为1~len的子串的最大个数

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
const int INF=0x3f3f3f3f;
int ans[MAX];
struct Tire
{
    static const int MAXN=26;
    int nxt[MAX][MAXN],f[MAX],L[MAX],rt[MAX],in[MAX],last,tot;
    void init()
    {
        last=tot=0;
        memset(nxt[0],-1,sizeof(nxt[0]));
        f[0]=-1;L[0]=0;
    }
    void add(int x)
    {
        int p=last,np=++tot;
        L[np]=L[p]+1;
        memset(nxt[np],-1,sizeof(nxt[np]));
        rt[np]=1;
        while(~p&&nxt[p][x]==-1) nxt[p][x]=np,p=f[p];
        if(p==-1) f[np]=0;
        else
        {
            int q=nxt[p][x];
            if(L[q]!=L[p]+1)
            {
                int nq=++tot;
                memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
                L[nq]=L[p]+1;
                f[nq]=f[q];
                f[q]=f[np]=nq;
                while(~p&&nxt[p][x]==q) nxt[p][x]=nq,p=f[p];
            }
            else f[np]=q;
        }
        last=np;
    }
    void cal()//topsort
    {
        memset(in,0,sizeof(in));
        for(int i=1;i<=tot;++i) ++in[f[i]];
        queue<int >q;
        for(int i=1;i<=tot;++i) if(!in[i]) q.push(i);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            if(f[u]==-1) continue;
            rt[f[u]]+=rt[u];
            if(--in[f[u]]==0) q.push(f[u]);
        }
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=tot;++i) ans[L[i]]=max(ans[L[i]],rt[i]);
    }
}SAM;
char s[MAX];
int main()
{
    while(~scanf("%s",s))
    {
        SAM.init();
        int len=strlen(s);
        for(int i=0;i<len;++i) SAM.add(s[i]-'a');
        SAM.cal();
        for(int i=len-1;i>=1;--i) ans[i]=max(ans[i],ans[i+1]);
        for(int i=1;i<=len;++i) printf("%d\n",ans[i]);
    }
    return 0;
}