HDU4622_Reincarnation

题目给出一个长为2000的字符串，和10000询问，每次询问从第l到第r个字符中间有多少个不同的子串。

其实，全部预处理。f[i][j]表示从i到j个字符的子串数。重构2000遍SAM。

对于新加入的字符，其所对应的last点，新增加的新子串数位step[last]-step[pre[last]]。原因嘛，自己想想就知道了。

不知道hdu上那种100ms+的代码是咋写出来的，求指教。

 

召唤代码君：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10010
using namespace std;

int next[maxn][26],pre[maxn],step[maxn];
int f[2002][2002];
char s[maxn];
int Q,N,last,T,l,r;
int p,q,np,nq;

int add()
{
    N++;
    for (int i=0; i<26; i++) next[N][i]=0;
    pre[N]=step[N]=0;
    return N;
}

int insert(int x)
{
    p=last,np=add(),step[np]=step[last]+1,last=np;
    while (p!=-1 && next[p][x]==0) next[p][x]=np,p=pre[p];
    if (p==-1) return step[np];
    q=next[p][x];
    if (step[q]==step[p]+1) { pre[np]=q; return step[np]-step[pre[np]]; }
    nq=add(),step[nq]=step[p]+1,pre[nq]=pre[q];
    for (int i=0; i<26; i++) next[nq][i]=next[q][i];
    pre[np]=pre[q]=nq;
    while (p!=-1 && next[p][x]==q) next[p][x]=nq,p=pre[p];
    return step[np]-step[pre[np]];
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",s+1);
        for (int i=1; s[i]; i++)
        {
            N=-1;N=add();last=0;pre[0]=-1;
            for (int j=i; s[j]; j++) f[i][j]=insert(s[j]-'a');
        }
        for (int i=1; s[i]; i++)
            for (int j=i+1; s[j]; j++) f[i][j]+=f[i][j-1];
        scanf("%d",&Q);
        while (Q--)
        {
            scanf("%d%d",&l,&r);
            printf("%d
",f[l][r]);
        }
    }
    return 0;
}