最小表示法加后缀自动机

poj1509.cpp

/*
Source Code

Problem: 1509  	User: WCMG
Memory: 2968K		Time: 829MS
Language: G++		Result: Accepted
Source Code
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 20010 
struct sam{
    sam *go[26],*f;
    int p,l;
}S[N],*root,*last;
char str[N];
int cnt,len;
void add(int x)
{
    cnt++;sam *p=&S[cnt],*jp=last;
    p->l=p->p=jp->l+1;last=p;
    for(;jp&&!jp->go[x];jp=jp->f)jp->go[x]=p;
    if(!jp)p->f=root;
    else if(jp->go[x]->l==jp->l+1)p->f=jp->go[x];
    else {
        cnt++;sam *r=&S[cnt],*q=jp->go[x];
        *r=*q;r->l=jp->l+1;r->p=p->p;
        q->f=p->f=r;
        for(;jp&&jp->go[x]==q;jp=jp->f)jp->go[x]=r;
    }
}void init()
{
    memset(S,0,sizeof(S));
    scanf("%s",str);
    root=last=&S[cnt=0];
    for(int i=0;i<strlen(str);i++)add(str[i]-'a');
    for(int i=0;i<strlen(str);i++)add(str[i]-'a');
}
void go()
{
    sam *x=root;
    for(int i=0;i<strlen(str);i++)
     for(int j=0;j<26;j++)
      if(x->go[j]){x=x->go[j];break;}
    printf("%d\n",x->p-strlen(str)+1);
}int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)init(),go();
}