玲珑OJ-1100 - 萌萌哒的第五题（kmp+dp）

Time Limit：10s Memory Limit：128MByte

Submissions：372Solved：86

给出一个长度为m的字符串，请问有多少个长度为n的字符串不存在子串等于给出的字符串。为了简化问题，我们规定所有字符串只包含小写英文字母。输入数据：包含多组输入数据(<=15)，每组数据：第一行包含两个整数n和m(1 <= n,m <= 1000)第二行包含一个长度为m的字符串，只含有小写字母。

SOLUTION

题解：http://www.ifrog.cc/acm/solution/16

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define maxn 1005#define Mod 1000000007int n,m,p[maxn],dp[maxn][maxn],c[maxn][30];char a[maxn];void kmp(){	int i,j=0;	p[j]=0;	for(i=2;i<=m;i++)	{		while(j>0 && a[j+1]!=a[i])			j=p[j];		if(a[j+1]==a[i])			j++;		p[i]=j;	}}int  main(){	int i,ans,j,k;	while(scanf("%d%d",&n,&m)!=EOF)	{		ans=0;		memset(dp,0,sizeof(dp));		scanf("%s",a+1);		kmp();		for(i=1;i<=m;i++)		{			for(j=0;j<26;j++)			{				int tmp=i,t=j+'a';				while(tmp>0 && a[tmp]!=t)				{					tmp=p[tmp-1]+1;					if(tmp==1 && a[tmp]!=t)					{						tmp=0;						break;					}				}				c[i][j]=tmp;			}		}		dp[0][0]=1;		for(i=1;i<=n;i++)			for(j=1;j<=m;j++)				 for(k=0;k<26;k++)				 {					 int t=k+'a';					 dp[i][c[j][k]]=(dp[i][c[j][k]]+dp[i-1][j-1])%Mod;				 }		for(i=0;i<m;i++)			ans=(ans+dp[n][i])%Mod;		PRintf("%d/n",ans);	}}