【BZOJ5337】[TJOI2018]str（动态规划，哈希）

题面

题解

就很呆。。。

显然按层\(dp\)，如果能够匹配上就进行转移，直接哈希判断是否能够匹配就好了。。。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MOD 1000000007

#define MAX 10010

#define ull unsigned long long

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

const ull base=297;

ull h[MAX],pw[MAX];

int n,m,ans,len;char s[MAX],ch[MAX];

int f[2][MAX];

ull Hash(int l,int r){return h[r]-h[l-1]*pw[r-l+1];}

int main()

{

	scanf("%d",&n);scanf("%s",s+1);len=strlen(s+1);

	pw[0]=1;for(int i=1;i<=len;++i)pw[i]=pw[i-1]*base;

	for(int i=1;i<=len;++i)h[i]=h[i-1]*base+s[i];

	int nw=1,pw=0;

	for(int i=0;i<=len;++i)f[0][i]=1;

	while(n--)

	{

		scanf("%d",&m);for(int i=0;i<=len+1;++i)f[nw][i]=0;

		while(m--)

		{

			scanf("%s",ch+1);int l=strlen(ch+1);

			ull val=0;for(int i=1;i<=l;++i)val=val*base+ch[i];

			for(int i=1;i+l-1<=len;++i)if(Hash(i,i+l-1)==val)add(f[nw][i+l],f[pw][i]);

		}

		nw^=1;pw^=1;

	}

	for(int i=1;i<=len+1;++i)add(ans,f[pw][i]);

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

	return 0;

}

秒客网

【BZOJ5337】[TJOI2018]str（动态规划，哈希）

【BZOJ5337】[TJOI2018]str（动态规划，哈希）

题面

题解

相关文章