hdu 6068 Classic Quotation

题

　　QAQ http://acm.hdu.edu.cn/showproblem.php?pid=6068

　　2017 Multi-University Training Contest - Team 4 - 1005

解

　　贴一张官方题解

　　

　　其中S可以由O(n*m)的求前缀得到。

　　求suf贼难，淦。

　　求suf主要是通过类似DP的思想

　　其中ismatch[i][j]表示T的匹配指针为i，匹配到字母j的时候，是否新匹配了一个完整的T串。

　　nxt2[i][j]表示，当T的匹配指针为i，匹配到字母j的时候，T的指针转移到哪个位置

　　然后未求前缀的suf数组就可以倒着DP出来了

　　（思路来自某官方题解和某其他博客的题解）

　　

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int M=5e4+44;

const int N=244;

int n,m,qur;

char S[M],T[N];

int nxt[N];

int preg[M];

int s[M][N];

int suf[M][N];

int ismatch[N][N],nxt2[N][N];

void init()

{

	int i,j,k,tmp,tmpi,tmpj;

	//get the nxt of T

	nxt[1]=0; k=0;

	for(j=2;j<=m;j++)

	{

		while(k && T[k+1]!=T[j])

			k=nxt[k];

		if(T[k+1]==T[j])

			k++;

		nxt[j]=k;

	}

	//get preg,s

	j=0;

	tmp=0;

	memset(s,0,sizeof(s));

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

	{

		while(j && T[j+1]!=S[i])

			j=nxt[j];

		if(T[j+1]==S[i])

			j++;

		if(j==m)

		{

			tmp++;

			j=nxt[j];

		}

		preg[i]=tmp; s[i][j]++;

	}

	for(i=2;i<=n;i++)

		for(j=0;j<m;j++)

			s[i][j]+=s[i-1][j];

	for(i=2;i<=n;i++)

		preg[i]+=preg[i-1];

	//get suf

	for(i=0;i<m;i++)

		for(j='a';j<='z';j++)

		{

			ismatch[i][j]=0;

			k=i;

			while(k!=0 && T[k+1]!=j)

				k=nxt[k];

			if(T[k+1]==j)

				k++;

			if(k==m)

			{

				ismatch[i][j]=1;

				k=nxt[k];

			}

			nxt2[i][j]=k;

		}

	for(i=0;i<m;i++)

		suf[n+1][i]=0;

	for(i=n;i>=1;i--)

		for(j=0;j<m;j++)

			suf[i][j]=ismatch[j][S[i]]+suf[i+1][nxt2[j][S[i]]];

	for(i=n;i>=1;i--)

		for(j=0;j<m;j++)

			suf[i][j]+=suf[i+1][j];

}

void solve()

{

	int i,j,L,R;

	ll ans;

	while(qur--)

	{

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

		ans=1ll*(n-R+1)*preg[L];

		for(i=0;i<m;i++)

			ans+=1ll*s[L][i]*suf[R][i];

		printf("%lld\n",ans);

	}

}

int main()

{

	int i,j,cas;

	scanf("%d",&cas);

	while(cas--)

	{

		scanf("%d%d%d",&n,&m,&qur);

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

		init();

		solve();

	}

	return 0;

}