状态机dp 你现在需要设计一个密码，需要满足; 的长度是 只包含小写英文字母 不包含子串
例如： 和 是 的子串， 不是 的子串。 请问共有多少种不同的密码满足要求? 由于答案会非常大，请输出答案模的余数。
数据范围
, 是 的长度 只包含小写英文字母
输入格式
输出格式
一个数，表示总方案数模
样例1
输入：
2
a输出：
625样例2
输入：
4
cbc输出：
456924样例3
输入：
3
xy输出：
17524样例4
输入：
50
password输出：
448890425思路
简单看一下案例1, 显然所有不包含子串a的长度为2的S, 其数量就是 25*25 = 625（去掉a后就剩下25个字母能选）。
边构造边判断是否为字串, 判断子串则可以使用KMP算法。
KMP算法过程是： 先构建模板n
for(int i = 1, j = 0; i <= m; i++)
{
while(j && s[i] != s[j + 1]) j = ne[j];
if(s[i] == s[j + 1]) j++;
ne[i] = j;
}接着对于目标字符串q
for(int i = 0, j = -1 ; i <= n; i++)
{
while(j != -1 && q[i] != s[j + 1]) j = ne[j];
if(q[i] == s[j +1]) j++;
if(m == j) cnt++; // 子串数加一
}如何得到所有长度为n的S串呢？普通循环是不行的, 这里需要使用DFS深搜来枚举。 其时间复杂度为 。显然是不行的。 既然需要从所有状态中得到可行状态, 那有没有方法可以直接根据可行状态开始计算呢？从一个可行状态转移到另一个可行状态, 直到得到所有可行状态。
需要从T串入手： 可行状态肯定满足KMP匹配的模板串长度小于m, 也就是说所有长度小于m的情况都是可行状态。
这些状态之间有什么关系呢？
KMP的匹配过程其实就是一个状态自动机, 在j位置上如果不能调到j+1, 则调到 ne[j]。即长度为j时可以转移到长度为j+1或长度为ne[j]。
设 为可行状态的长度为j时的方案
可得：
在结尾时将所有长度情况的可行状态的方案数加起来, 就是总方案数。
而对于每个i, 都有26种对应的可行状态, 因此状态定义为：
f[i][j]： 已经确定i长度, 且其匹配的s串位置为j, 要枚举i+1的字符。
此时所谓的确定的i长度p串, 匹配的j长度s串都是抽象的, 但一定存在。
初始状态：f[0][0] = 1
最终答案：sum(f[n][i]) i = (0,1,2,...,m-1)
状态更新：
令 u = j, 维持状态恒定
当p[i + 1] != s[u + 1]时, 执行u = ne[u], 直到相等为止
相等后将u++
此时说明f[i + 1][u] 可以从 f[i][j] 也就是当前状态 转移而来。
则将f[i + 1][u] += f[i][j]
该题的DP模式是刷表法, 即用一个状态去更新以后的状态, 而不是根据之前确定的状态来设定当前的状态（填表法）。
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
//------- Coding Area ---------//
const int N = 55, mod = 1e9 + 7;
int n, m;
char T[N];
int ne[N];
long long ans = 0;
int f[N][N];
int main()
{
cin >> n >> T + 1;
m = strlen(T + 1);
for (int i = 2, j = 0; i <= m; i++)
{
while (j && T[i] != T[j + 1])
j = ne[j];
if (T[i] == T[j + 1])
j++;
ne[i] = j;
}
f[0][0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i && j < m; j++)
{
for (char c = 'a'; c <= 'z'; c++)
{
int u = j;
while (u && T[u + 1] != c)
u = ne[u];
if (T[u + 1] == c)
u++;
if (u < m)
f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
}
}
}
for (int i = 0; i < m; i++)
ans = (ans + f[n][i]) % mod;
cout << ans << endl;
return 0;
}