考察:有限状态机dp+kmp
鬼才想得到的解法
思路:
在验证某串a是否为b的子串时,常常使用kmp算法.当子串匹配下标j = 子串长度时,说明串a是串b的子串.如果i取到串b的最后一位时,j还没有 = a长度,说明a不是b的子串.
在这道题,我们需要构造串b,使得a不是b的子串,也就是j不能取到串a的长度.假设当前j是a的待匹配位,b的下一位构造位为i.第i位有26种取值,对于每个取值,j的下一步位置大多不同.将下一步的取值看成转化的状态的话,就能构造f[i][j]表示b构造了前i个字符,匹配了a子串的前j位.那么f[i][j] += f[i-1][k].
因为第i个字符是需要枚举a~z的,取到a[k]后要做一次kmp匹配,求第i位可以匹配的位置.
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 const int N = 55,Mod = 1e9+7; 5 char s[N];//f[i][j]表示构造前i个字符匹配前j个字符的方法数 6 int n,ne[N],len,f[N][N]; 7 void init() 8 { 9 for(int i=0,j=2;j<=len;j++) 10 { 11 while(i&&s[i+1]!=s[j]) i = ne[i]; 12 if(s[i+1]==s[j]) i++; 13 ne[j] = i; 14 } 15 } 16 int main() 17 { 18 scanf("%d%s",&n,s+1); 19 len = strlen(s+1); 20 init(); 21 f[0][0] = 1; 22 for(int i=1;i<=n;i++)//已经构造了i个字符. 23 for(int j=0;j<len;j++)//j是已经子串匹配了的位置 24 for(char k=‘a‘;k<=‘z‘;k++)//枚举密码的下一个字符是k. 25 { 26 int t = j; 27 while(t&&s[t+1]!=k) t = ne[t]; 28 if(s[t+1]==k) t++; 29 f[i][t] += f[i-1][j];//构造了密码前i个字符,最后一个字符与子串匹配了j个 30 f[i][t]%=Mod; 31 } 32 int res = 0; 33 for(int i=0;i<len;i++) res+=f[n][i],res%=Mod; 34 printf("%d\n",res); 35 return 0; 36 }