思路
1.状态机
动态规划
为什么这样的状态表示是可行的呢?
因为S数组中的第n位有26个小写字母,匹配在T中的位置一定存在(因为不匹配,匹配到的位置是0),
所以把所有f[n][0~m-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=0;i<n;i++)//枚举密码位
for(int j=0;j<m;j++)//把第i位密码匹配到的子串位置都枚举一遍
//j表示第i位密码匹配到的位置,因为不能包含子串,所以不能匹配到m这个位置
for(char k='a';k<='z';k++)//把第i+1所有可能的字母都枚举一遍
{
//匹配过程:寻找当第i+1的位置是k时,并且密码已经生成了第i位,匹配的子串的位置是j时,能跳到哪个位置
int u=j;
while(u&&str[u+1]!=k) u=ne[u];
if(str[u+1]==k) u++;
if(u<m) f[i+1][u]=(f[i+1][u]+f[i][j])%mod;
//因为是从f[i][j](i+1的位置为k)跳到f[i+1][u]这个位置,所以f[i+1][u]=f[i+1][u]+f[i][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;
}
K 总说过不偷懒的话,可以预处理出所有的 26 * m * n 种情况,有人试过吗
K总??
你个假粉丝,明明是J总
明明是A总
不是X总?
明明是Orz总(恼)
const int N=55;
int jump[N][26];
int ne[N];
char str[N];
int n,m;
int f[N][N];
int mod=1e9+7;
int main()
{
cin>>n>>(str+1);
m=strlen(str+1);
for(int i=2,j=0;i<=m;i)
{
while(j&&str[i]!=str[j+1])j=ne[j];
if(str[j+1]==str[i])j;
ne[i]=j;
}
for(int i=0;i<=m;i)
{
for(char j=’a’;j<=’z’;j)
{
int u=i;
while(u&&j!=str[u+1])u=ne[u];
if(str[u+1]==j)u;
jump[i][j-‘a’]=u;
}
}
f[0][0]=1;
for(int i=0;i<n;i)
{
for(int j=0;j<m;j)
{
for(int k=0;k<26;k)
{
int u=jump[j][k];
if(u<m)f[i+1][u]=(f[i+1][u]+f[i][j])%mod;
}
}
}
int res=0;
for(int i=0;i<m;i++)res=(res+f[n][i])%mod;
cout<<res;
}
跟优化kmp的ne数组一样,直接指向目标的匹配节点,y总ac自动机有讲
明明是B总
ennnnn…
正确答案是YXC总
不是D总吗?(*  ̄︿ ̄)
不是E总?
ABCDEFGHIJKLMNOPQRSTUVWXYZ总???
T总(tfeng)
我有一个问题,如果i<j的话怎么匹配呢?不要求j<=i么??
我也好奇,这里没搞懂
有佬知道为啥后面j是从0开始吗,j=0、不是没有存字符吗
0表示压根匹配不上的情况
大佬tql,一直没搞明白 j 为什么取不到 m,看了你的题解豁然开朗啊,orz!!!
大佬,能问一下这里的数量是不是状态数量相加
np,终于知道为啥要加上回退的方案了
清晰易懂,thx
n刷理解了
所以n等于多少
好好准备高考, 加油
请教一下大佬,上面说是有重边的情况我能理解(多个点指向一个点),但是要是一个点可以向前跳到多个点呢,这种情况不用更新所有吗,例如给一个例子abcabcabcddd,前面有三个abc,在遍历到第三个abc的时候为什么只跳到第二个abc而不更新第一个abc呢,求解
请问要是循环中的f[i+1][u]改为f[i][u]那转移方程怎么写呢(大雾),请高手帮帮我这个大蒟蒻。
int main(){ cin >> n >> str; int m = strlen(str); for(int i = 0, j = 1; j < n; j++){ while(i && str[i] != str[j]) i = ne[i - 1]; if(str[i] == str[j]) ++i; ne[j] = i; } dp[0][0] = 1; for(int i = 1; i <= n; i++) for(int j = 0; j < m; j++) for(int k = 'a'; k <= 'z'; k++){ int u = j; while(u && k != str[u]) u = ne[u - 1]; if(k == str[u]) ++u; if(u < m) dp[i][u] = (dp[i][u] + dp[i - 1][j]) % mod; } int ans = 0; for(int i = 0; i < m; i++) ans = (ans + dp[n][i]) % mod; cout << ans; }
u+1和u感觉都是kmp的定义决定而已 匹配的模式串和主串得问题
没那么神奇,可以一直过掉的
#include <bits/stdc++.h> using namespace std; const int N = 55; const int MOD = 1e9 + 7; int n, ne[N]; int f[N][N]; char p[N]; int res; int main() { scanf("%d %s", &n, p + 1); int m = strlen(p + 1); for (int i = 2, j = 0; i <= m; i++) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j++; ne[i] = j; } f[0][0] = 1; for (int i = 1; i <= n; i++) for (int j = 0; j < m && j < i; j++) for (char ch = 'a'; ch <= 'z'; ch++) { int u = j; while (u && ch != p[u + 1]) u = ne[u]; if (ch == p[u + 1]) u++; f[i][u] = (f[i][u] + f[i - 1][j]) % MOD; } for (int i = 0; i < m; i++) res = (res + f[n][i]) % MOD; printf("%d\n", res); return 0; }
状态图画得很好. 不然我得在第二维想很久了. nice
写的不错,清晰
%%%%
好棒的题解,爱了
感谢🙏
怎么我感觉看了千篇一律的题解但是就状态定义第一眼我就看不懂了,不知道题解怎么理解的。
大佬,太强啦
%%%%%%%%%
很详细,超赞~
%%%%%%%%%%%%%%%
太棒了~