【hdu4622】Reincarnation

2015.06.16 19:31 Tue | 25次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给出一个字符串,最长2000,q个询问,每次询问[l,r]区间内有多少个不同的字串。q<=10000
题解
这也算是第一道完全自己想自己写的后缀自动机了,虽然还没完全理解透,但a掉这种简单题还没啥问题的。
由于n只有2000,所以我们把询问按l排序,如果l和上一个不同了,就重建自动机。
由于后缀自动机上不会有两个相同的状态,所以每个节点的len减去父亲节点的len就是这个节点单独包含的子串数,这个在插入的过程中顺便维护一下就好了

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 4005
using namespace std;
int T,Q,len;
char s[N];
struct Que
{
    int l,r,id;
}q[10005];
int ans[10005];
bool cmp(const Que &a,const Que &b)
{
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}
struct SAM
{
    int len[N],son[N][26],fa[N];
    int last,tot,ret;
    void init()
    {
        last=tot=1;ret=0;
        memset(son,0,sizeof(son));
        memset(fa,0,sizeof(fa));
        memset(len,0,sizeof(len));
    }
    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,ret+=len[np];
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q,ret+=len[np]-len[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;
                ret+=len[np]-len[nq];
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        } 
    }
    void get_ans(int x)
    {
        ans[x]=ret;
    }
}sam;
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%s",s);len=strlen(s);
        cin>>Q;
        for(int i=1;i<=Q;i++) 
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].l--;q[i].r--;
            q[i].id=i;
        }
        sort(q+1,q+Q+1,cmp);q[0].l=-1;
        for(int i=1;i<=Q;i++)
        {
            if(q[i].l!=q[i-1].l) 
            {
                sam.init();
                for(int j=q[i].l;j<=q[i].r;j++) sam.insert(s[j]-'a');
                sam.get_ans(q[i].id);
            }
            else
            {
                for(int j=q[i-1].r+1;j<=q[i].r;j++) sam.insert(s[j]-'a');
                sam.get_ans(q[i].id);
            }
        }
        for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
    }
}```