玲珑杯round11-E：萌萌哒的第五题

Time Limit：10s Memory Limit：128MByte

Submissions：351Solved：74

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

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

c[i][k]表示前i-1个字符和m串前i-1个字符完全相同，而第i个字符为k和m串前缀匹配的最长长度

dp[i][j]表示长度为i的字符串中不存在子串m并且所有后缀中与m的前缀匹配的最长长度为j

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define mod 1000000007char ch, str[1005];int dp[1005][1005], c[1005][156], net[1005];int main(void){	int n, m, i, j, p, q, ans;	while(scanf("%d%d%s", &n, &m, str+1)!=EOF)	{		memset(dp, 0, sizeof(dp));		p = 0, q = 1, net[1] = 0;		while(q<=m)		{			if(p==0 || str[p]==str[q])			{				net[++q] = ++p;				if(str[p]==str[q])					net[q] = net[p];			}			else				p = net[p];		}		for(i=1;i<=m;i++)		{			for(ch='a';ch<='z';ch++)			{				p = i;				while(p!=0 && str[p]!=ch)					p = net[p];				c[i][ch] = p;			}		}		dp[0][0] = 1;		for(i=1;i<=n;i++)		{			for(j=1;j<=m;j++)			{				for(ch='a';ch<='z';ch++)					dp[i][c[j][ch]] = (dp[i][c[j][ch]]+dp[i-1][j-1])%mod;			}		}		ans = 0;		for(i=0;i<=m-1;i++)			ans = (ans+dp[n][i])%mod;		PRintf("%d/n", ans);	}	return 0;}