【poj1743】Musical Theme

2015.06.16 09:52 Tue | 16次阅读 | 旧日oi | 固定链接 | 源码

题目大意 给定一个序列,求最长的重复出现的序列,不能相交。
题解
后缀自动机第一题。。其实只是刚刚理解了后缀自动机的建法,至于能干什么还完全不知道……看hzwer的题解说求最先出现的位置和最后出现的位置,只是感觉似乎是那么回事,但是并没有想的十分清楚,再做几道题看看吧。
贴个模板。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 40005
#define inf 0x3f3f3f3f
int n,a[N];
struct SAM
{
    int l[N],r[N],son[N][180],fa[N],len[N],v[N],q[N];
    int last,tot;
    void init()
    {
        memset(v,0,sizeof(v));
        for(int i=1;i<=2*n;i++) memset(son[i],0,sizeof(son[i]));
        l[1]=inf,r[1]=0;last=tot=1;
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        l[np]=r[np]=len[np];
        while(!son[p][x]&&p) son[p][x]=np,p=fa[p];
        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;l[nq]=inf,r[nq]=0;
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];fa[np]=fa[q]=nq;
                while(son[p][x]==q) son[p][x]=nq,p=fa[p];
            }
        }
    }
    void solve()
    {
        for(int i=1;i<=tot;i++) v[len[i]]++;
        for(int i=1;i<=n;i++) v[i]+=v[i-1];
        for(int i=tot;i;i--) q[v[len[i]]--]=i;
        for(int i=tot;i;i--)
        {
            int p=q[i];
            l[fa[p]]=min(l[p],l[fa[p]]);
            r[fa[p]]=max(r[p],r[fa[p]]);
        }
        int ans=0;
        for(int i=1;i<=tot;i++)
        ans=max(ans,min(len[i],r[i]-l[i]));
        if(ans<4) puts("0");
        else printf("%d\n",ans+1);
    }
}sam;
int main()
{
    while(cin>>n&&n)
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<n;i++) a[i]=a[i+1]-a[i]+88;
        sam.init();
        for(int i=1;i<n;i++) sam.insert(a[i]);
        sam.solve();
    }
}```