HDU4622 Reincarnation 字符串 SAM

原文链接https://www.cnblogs.com/zhouzhendong/p/HDU4622.html

题目传送门 - HDU4622

题意

　　多组数据。

　　对于每一组数据，给定一个字符串 s ，以及 m 次询问，每次询问 s 的一个子串的不同子串个数。

　　$|s|\leq 2000,m\leq 10000$

题解

　　直接 SAM 预处理一下每一个区间的答案就可以了。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2005;

int T,n,m;

LL now,ans[N][N];

struct SAM{

	int Next[26],fa,Max;

}t[N<<1];

char s[N];

int size;

void init(){

	memset(t,0,sizeof t);

	size=1,t[0].Max=-1;

	for (int i=0;i<26;i++)

		t[0].Next[i]=1;

}

int extend(int p,int c){

	if (t[p].Next[c]&&t[p].Max+1==t[t[p].Next[c]].Max)

		return t[p].Next[c];

	int np=++size,q,nq;

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

	for (;!t[p].Next[c];p=t[p].fa)

		t[p].Next[c]=np;

	q=t[p].Next[c];

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

		t[np].fa=q,now+=t[np].Max-t[q].Max;

	else {

		nq=++size;

		t[nq]=t[q],t[nq].Max=t[p].Max+1;

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

		now+=t[np].Max-t[nq].Max;

		for (;t[p].Next[c]==q;p=t[p].fa)

			t[p].Next[c]=nq;

	}

	return np;

}

int main(){

	scanf("%d",&T);

	while (T--){

		scanf("%s%d",s+1,&m);

		n=strlen(s+1);

		for (int i=1;i<=n;i++){

			now=0;

			init();

			for (int j=i,p=1;j<=n;j++){

				p=extend(p,s[j]-'a');

				ans[i][j]=now;

			}

		}

		while (m--){

			int L,R;

			scanf("%d%d",&L,&R);

			printf("%lld\n",ans[L][R]);

		}

	}

	return 0;

}