[JZOJ 4886 ]字符串

Description

某日mhy12345在教同学们写helloworld，要求同学们用程序输出一个给定长度的字符串，然而发现有些人输出了一些“危险”的东西，所以mhy12345想知道对于任意长度n的小写字母字符串，不包含危险串的字符串个数

Input

多组数据，以EOF结束。对于每组数据，第一行一个数n，表示字符串的长度，第二行一个字符串str表示危险串。

Output

对于每组数据，输出一个整数表示答案 mod (10^9+7)的值。

Sample Input

5 a

Sample Output

9765625

Data Constraint

对于10%的数据，|str|=1 对于另30%的数据，n<=5 对于另30%的数据，危险串不存在相同字符 对于100%的数据，0<=|str|<=100,0<=n<=10000

The Solution

题目大意很显然，就是要求长度为n的字符串中，不包含给定子串的字符串个数。

对于30%的数据，直接暴力即可。 对于100%的数据。

我们可以设f[i][j]为做到字符串第i个，危险串匹配到第j个。 再设c[i][j]为危险串中做到了第i个之后，下一位选j会到第c[i][j]的位置。 即下一位选j所能到达的最远匹配位置。

对于一个危险字符串，我们可以考虑下一位选或是不选 当下一位选 s[j+1]时，转移到 f[i][j+1]； 当下一位选 s[1]时，转移到 f[i][1]； 当下一位选其他时，转移到 f[i][0]。 但是由于考虑到有重复字母，所以当下以为选其他时，不一定会装移到f[i][0] 有可能会联系到到危险子串的子串。（这就是kmp的思想了）

所以一开始f[0][0] = 1;

c数组可以用kmp的思想求出。

很显然可以得到一个dp方程为

f[i+1][c[j][k]]+=f[i][j]

k表示1~26个字母.

最后统计答案为

ans+=∑i=0len−1f[n][i]

len位危险子串长度

CODE

#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <cstring> #define fo(i,a,b) for (int i=a;i<=b;i++) #define fd(i,a,b) for (int i=a;i>=b;i--) #define N 10005 using namespace std; const int mo = 1e9+7; typedef long long ll; char s[N]; int a[N],p[N],n,len; ll ans = 0,f[N][105],c[N][26]; void Pre_kmp() { memset(p,0,sizeof(p)); int j = 0; fo(i,2,len) { if (j && s[j + 1] != s[i]) j = p[j]; if (s[j + 1] == s[i]) j ++; p[i] = j; } fo(i,0,len-1) fo(j,0,25) { int k = i; while (k && a[k + 1] != j) k = p[k]; if (a[k + 1] == j ) k ++; c[i][j] = k; } } int main() { freopen("helloworld.in","r",stdin); freopen("helloworld.out","w",stdout); while (scanf("%d",&n) != EOF) { ans = 0; scanf("%s",s + 1); len = strlen(s + 1); fo(i,1,len) a[i] = s[i] - 'a'; Pre_kmp(); memset(f,0,sizeof(f)); f[0][0] = 1; fo(i,0,n-1) fo(j,0,len-1) fo(k,0,25) f[i+1][c[j][k]] = (f[i+1][c[j][k]] + f[i][j]) % mo; fo(i,0,len-1) ans = (ans + f[n][i]) % mo; printf("%lld\n",ans % mo); } return 0; }