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);	}}