Kmp + 状态机模板题
判断是否含有子串的方法一般都用kmp,判断方法是看匹配完成之后字串的指针是否到达字串的长度m
KMP回顾参考 AcWing 831. KMP字符串
状态表示
f[i][j]
表示密码已经生成了i
位,并且第i
位已经匹配到了子串的位置为第j
位(相当于前
j个字符已经匹配上了)
的所有方案数
状态:构造第i位密码的时候可以分别用26个英文字母构造,所以26个不同的字母对应着26个状态
注意这里的第i位已经匹配到了子串的位置为第j位
说的是已经计算到的进度.
状态计算
初始化f[0][0] = 1
,表示已经匹配了0位,且匹配的子串的位置是0时的方案数为1
求解的过程(核心):
利用kmp每次往后跳到密码串可以与T串匹配的最低字符数next[j]处,然后将这个当前状态累加到f[i - 1][next[j]]里面去,
或者往前跳比较下一个字符,相等则表示密码串可以与T串匹配的字符数是j++,否则就是j
假设当前的密码串构造到第一位(i)
是"a"
,而当前字串子串T
匹配到的位置0(j)
的字符为"b"
,
不相等,那么运用kmp算法就会一直跳到u = next[0] = 0
,而当前的f[1][0] += f[0][0]【f[i][j] += f[i -1][u]】
,接着枚举i
的26个可能的字母,f[1][0]
就加了25遍f[0][0]
,这些就是f[1][0]
:表示构造了1位密码的情况下与T
中一个字符都没有匹配到的所有方案数,除了枚举到密码串为"b"
的时候j
跳到1
,方案数等于f[1][1] += f[0][0]
:就表示构造了1位密码时匹配到了T
中一个字符的所有方案数,计算n
位密码能匹配到m - 1
位T的字符的方案数过程同上。
最后,因为密码S
不管能匹配到字串T
的多少位,只要不超过m
位,最后都是算不包含子串T
,所以枚举0 ~ m - 1
,即是0 ~ n
位密码能匹配到了T
中0 ~ m - 1
个字符的所有方案数
c++代码
状态的转移类似背包问题,i的状态由i - 1转移过来
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=55,mod=1e9+7;
int f[N][N],ne[N];
char str[N];//子串
int main()
{
int n,m;
cin>> n >> str+1;
m = strlen(str+1);
for(int i=2,j=0;i<=m;i++)//求出ne数组(kmp模板)
{
while(j && str[j+1] != str[i]) j = ne[j];
if(str[j+1] == str[i]) j++;
ne[i] = j;
}
f[0][0]=1;//已经匹配了0位,且匹配的子串的位置是0时的方案数为1;(初始化)
for(int i=1;i<=n;i++)//枚举密码位
for(int j=0;j<m;j++)//把第i位密码匹配到的子串位置都枚举一遍
//j表示第i位密码匹配到的位置,因为不能包含子串,所以不能匹配到m这个位置
for(char k='a';k<='z';k++)//把第i所有可能的字母都枚举一遍
{
//匹配过程:寻找当第i的位置是k时,并且密码已经生成了第i - 1位,匹配的子串的位置是j时,能跳到哪个位置
//两种可能:往前跳,往后跳
int u = j;
while(u&&str[u+1] != k) u = ne[u];
if(str[u+1] == k) u++;
if(u<m) f[i][u] = (f[i][u] + f[i - 1][j]) % mod;
//因为是从f[i - 1][j](i的位置为k)跳到f[i][u]这个位置,所以f[i][u]=f[i][u]+f[i - 1][j];
/*
注:可能存在重边,因为j不同但ne[j]是相同的,并且k是相同的,所以此时
f[i][j1]和f[i][j2]跳到的位置是一样的(k相同,ne[j1]=ne[j2])
*/
}
int res=0;
for(int i=0;i<m;i++) res=(res+f[n][i])%mod;
//将所有的方案数加起来即为总方案数
printf("%d",res);
return 0;
}
总算看懂了
%%%
字串子串T匹配到的位置0(j)的字符为”b”,不相等,那么运用kmp算法就会一直跳到u = next[0] = 0; 此处j的位置是0了 不会跳的
这个是最符合之前的思维逻辑的。
状态计算的图的(1) 和 (2)是不是写反了? (1)应该是表示u跳到了j++ (2)表示第j+1位没匹配上 j=next[j] . 还是我这里理解的不对?
你是对的,楼主写反了
清晰
orz