首页 > 代码库 > HDU4622_Reincarnation

HDU4622_Reincarnation

2024-07-09 00:01:29   221人阅读

题目给出一个长为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 10010using 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\n",f[l][r]);        }    }    return 0;}

　　


联系
我们