【HDU4622】Reincarnation

【HDU4622】Reincarnation

一眼似乎不可做，但发现\(strlen(x)\)很小，暴力\(O(n^2)\)预处理每个区间\((l,r)\)，查询时\(O(1)\)输出就好了

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<iostream>

typedef int LL;

const LL maxn=2010;

inline LL Read(){

	LL x=0,f=1; char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0'&&c<='9')

	    x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x*f;

}

struct node{

	LL len,fail;

	LL son[26];

}t[maxn<<1];

LL n,m,T,nod,last;

LL ans[maxn][maxn];

char s[maxn];

inline void Insert(LL c){

	LL np=++nod,p=last;

	last=np;

	t[np].len=t[p].len+1;

	while(p&&!t[p].son[c]){

		t[p].son[c]=np,

		p=t[p].fail;

	}

	if(!p)

	    t[np].fail=1;

	else{

		LL q=t[p].son[c];

		if(t[q].len==t[p].len+1)

		    t[np].fail=q;

		else{

			LL nq=++nod;

		    t[nq]=t[q];

		    t[nq].len=t[p].len+1;

		    t[np].fail=t[q].fail=nq;

		    while(p&&t[p].son[c]==q){

		    	t[p].son[c]=nq,

		    	p=t[p].fail;

			}

		}

	}

}

int main(){

	T=Read();

	while(T--){

		scanf(" %s",s+1);

		LL Len=strlen(s+1);

		for(LL i=1;i<=Len;++i){

			nod=last=1;

			memset(t,0,sizeof(t));

			for(LL j=i;j<=Len;++j){

				Insert(s[j]-'a'),

				ans[i][j]=ans[i][j-1]+t[last].len-t[t[last].fail].len;

			}

		}

		m=Read();

		while(m--){

			LL l=Read(),r=Read();

			printf("%d\n",ans[l][r]);

		}

	}

	return 0;

}