【spoj1811&&1812&&8222&&7258】后缀自动机四连击

2015.06.16 17:10 Tue | 22次阅读 | 旧日oi | 固定链接 | 源码

刷了一天的后缀自动机,算法理解度直线上升,感觉差不多有50%了,晚上继续!
spoj1811
求两个串的最长公共子串。
题解
事先声明:本人不保证题解中不会出现重大学术问题,求神犇不D,有问题的或理解有误的地方望大家指出。
把第一个串建成后缀自动机,然后在上面匹配第二个串s2。
先设一个p指针指向后缀自动机的根,然后从头扫描第二个串,如果有son[p][s2[i]]非空,那么就说明在p前面塞一个s2[i]之后后缀自动机依然能接受这个串,通俗点说就是有这个串,有人可能会有疑问不是从前往后匹配的吗?不是应该在后面塞吗?然而后缀自动机每次加入一个后缀本身就是逆向加的了,所以逆向在前面塞不就相当于在后面塞嘛。如果son[p][s2[i]]非空,那么lcs++,同时让p=son[p][s2[i]],然后重复这一过程,如果不存在son[p][i]了,那么就说明匹配进行不下去了,那么我们就需要找p的父亲节点,假设p代表ababbaad,那么p的父亲节点可以是当前p代表的串的后缀,比如abbaad,很显然p的这些后缀都可以和s2当前以匹配的后k个字符匹配,k为p后缀的长度。如果p的某个祖先f存在son[f][s2[i]],那么p就等于son[f][s2[i]],同时将lcs变成len[f]+1,如果找不到这样一个祖先,把lcs清0,p重新变成根节点。这样问题就解决了。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char s1[250005],s2[250005];
int len,len2,ans;
struct SAM
{
    int son[550005][26],fa[550005],len[550005];
    int last,tot;
    void init()
    {
        last=tot=1;
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q;
            else
            {
                int nq=++tot;len[nq]=len[p]+1;
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        }
    }
    void solve()
    {
        int lcs=0,p=1;
        for(int now,i=0;i<len2;i++)
        {
            now=s2[i]-'a';
            if(son[p][now])
            {
                lcs++;
                ans=max(ans,lcs);
                p=son[p][now];
            }
            else
            {
                while(p&&!son[p][now]) p=fa[p];
                if(p)
                {
                    lcs=len[p]+1;
                    p=son[p][now];
                    ans=max(ans,lcs);
                }
                else lcs=0,p=1;
            }
        }
        printf("%d\n",ans);
    }
}sam;
int main()
{
    scanf("%s%s",s1,s2);
    len=strlen(s1);len2=strlen(s2);
    sam.init();
    for(int i=0;i<len;i++) sam.insert(s1[i]-'a');
    sam.solve();
}
spoj1812
求多个串的最长公共子串。
题解
还是把第一个串建成后缀自动机,然后基数排序求出len的顺序,然后对每个串执行上一题的匹配过程,同时对于每个点记录在当前点最多能匹配多长。
对于每个串,执行完匹配过程后,更新答案,对于一个节点pp的最大匹配长度可以用来更新fa[p]的最大匹配长度,这个很显然。然后对每个pp的最大匹配长度和p代表的串的最长长度的min
最后求每个点能匹配的最长长度的最大值就行了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200005
char s[N];
int len;
struct SAM
{
    int son[N][26],len[N],fa[N];
    int rk[N],ans[N],v[N];
    int tot,last;
    void init()
    {
        last=tot=1;
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q;
            else
            {
                int nq=++tot;len[nq]=len[p]+1;
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        }
    }
    void work()
    {
        int l=strlen(s),lcs=0;
        for(int now,p=1,i=0;i<l;i++)
        {
            now=s[i]-'a';
            if(son[p][now])
            {
                lcs++;
                p=son[p][now];
                ans[p]=max(ans[p],lcs);
            }
            else
            {
                while(p&&!son[p][now]) p=fa[p];
                if(son[p][now])
                {
                    lcs=len[p]+1;
                    p=son[p][now];
                    ans[p]=max(ans[p],lcs);
                }
                else p=1,lcs=0;
            }
        }
        for(int i=tot;i;i--)
        {
            int k=rk[i];
            len[k]=min(len[k],ans[k]);
            ans[fa[k]]=max(ans[fa[k]],ans[k]);
            ans[k]=0;
        }
    }
    void solve(int L)
    {
        for(int i=1;i<=tot;i++) v[len[i]]++;
        for(int i=1;i<=L;i++) v[i]+=v[i-1];
        for(int i=tot;i;i--) rk[v[len[i]]--]=i;
        while(scanf("%s",s)!=EOF) work();
        int mx=0;
        for(int i=1;i<=tot;i++) mx=max(mx,len[i]);
        printf("%d\n",mx);
    }
}sam;
int main()
{
    scanf("%s",s);len=strlen(s);
    sam.init();
    for(int i=0;i<len;i++) sam.insert(s[i]-'a');
    sam.solve(len);
    return 0;
spoj8222
给定一个字符串,求出现次数最多的长度为 i 的子串的次数,i 的取值为 1 - lenlen表示这个字符串的长度。
题解
把串建成后缀自动机(这不是废话么),然后把节点按len基数排序,对于整个串的每个前缀(自动机内的每次加入的后缀),把ans值设为1
接下来的更新方法和上题类似,都是用k来更新fa[k]的值,详细过程看代码吧……
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char s[250005];
int len;
struct SAM
{
    int son[500005][26],len[500005],fa[500005];
    int c[500005],rk[500005],ans[500005],v[500005];
    int tot,last;
    void init()
    {
        last=tot=1;
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q;
            else
            {
                int nq=++tot;len[nq]=len[p]+1;
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        }
    }
    void solve(int L)
    {
        for(int i=1;i<=tot;i++) v[len[i]]++;
        for(int i=1;i<=L;i++) v[i]+=v[i-1];
        for(int i=tot;i;i--) rk[v[len[i]]--]=i;
        for(int p=1,i=0;i<L;i++) c[p=son[p][s[i]-'a']]++;
        for(int i=tot;i;i--)
        {
            int k=rk[i];
            ans[len[k]]=max(ans[len[k]],c[k]);
            c[fa[k]]+=c[k];
        }
        for(int i=1;i<=L;i++) printf("%d\n",ans[i]);
    }
}sam;
int main()
{
    scanf("%s",s);len=strlen(s);
    sam.init();
    for(int i=0;i<len;i++) sam.insert(s[i]-'a');
    sam.solve(len);
    return 0;
}
spoj7258
给定一个字符串,取出所有的子串按照字典序排序并去重后,求第K大的子串。
之前的过程不说了,看代码就能懂。但这题和前面有个很重大的不同,就是用len值大的更新len值小的地方不再是用k更新fa[k],是用son[k][i]来更新k,这是为什么呢?(以下纯属个人yy)因为这道题跟某个具体的点有了关系,而后缀自动机的点都是经过压缩的,所以如果按fa更新的话会少算很多很多。
诶呀好吧我也说不太明白了,其实我自己想的也不是太明白,再做几个题再说吧……
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 180005
char s[N];
int len;
struct SAM
{
    int son[N][26],len[N],fa[N];
    int rk[N],ans[N],v[N];
    long long num[N];
    int tot,last;
    void init()
    {
        last=tot=1;
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q;
            else
            {
                int nq=++tot;len[nq]=len[p]+1;
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        }
    }
    void prework(int L)
    {
        int i,k;
        for(i=1;i<=tot;i++) v[len[i]]++;
        for(i=1;i<=L;i++) v[i]+=v[i-1];
        for(i=tot;i;i--) rk[v[len[i]]--]=i;
        for(i=1;i<=tot;i++) num[i]=1;
        for(i=tot;i;i--)
        {
            k=rk[i];
            for(int i=0;i<26;i++)
            if(son[k][i]) num[k]+=num[son[k][i]];
        } 
    }
    void solve(int k)
    {
        int p=1,i,cnt=0;
        while(k)
        {
            for(i=0;i<26;i++)
            if(son[p][i])
            {
                if(num[son[p][i]]<k) k-=num[son[p][i]];
                else 
                {
                    ans[++cnt]=i;k--;
                    p=son[p][i];
                    break;
                }
            }
        }
        for(i=1;i<=cnt;i++) printf("%c",ans[i]+'a');
        puts("");
    }
}sam;
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%s",s);len=strlen(s);
    sam.init();
    int i,x,n;
    for(i=0;i<len;i++) sam.insert(s[i]-'a');
    sam.prework(len);
    scanf("%d",&n);
    for(i=1;i<=n;i++) 
    {
        scanf("%d",&x);
        sam.solve(x);
    }
    return 0;
}```