// 禁止字符串 字符串上的动态规划// 挑战程序设计第二版 page 368// 考虑只由'A','G','C','T'四种字符组成的DNF字符串// 给定一个长度为k的字符串S，计算长度恰好为n的且// 不包含S的字符串的个数输入结果对10009取膜// 1<=k<=100// 1<=n<=10000// // 这道题想动态规划，肯定是n*k的算法，，即10的七次方以内// 的复杂度//// 但是，之后就卡住了。。。//// 仔细研习了书上的思路，发现状态定义的有点巧妙// dp[i][j] 表示前i个字符最后面j个字符与S的前j个字符匹配的// 合法的字符串的数目// 则// dp[i+1][j] = sigma(dp[i][x])(0<=x<k)// // 书上的预处理十分巧妙 直接预处理出从某个状态后面添加一个字符// 所达到的状态的表//// 这个算法让我懂了挺多的，思路开阔了很多// 继续练吧。。。。//#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <iostream>using namespace std;int n,k;string S;const char *agct = "AGCT";const int maxn = 1009;int dp[maxn][108];int next[maxn][5];const int MOD = 10009;void init(){memset(dp,0,sizeof(dp));dp[0][0] = 1;}void solve(){for (int i=0;i<k;i++){for (int j=0;j<4;j++){// 取S的前i个元素并在后面添加一个元素string s = S.substr(0,i) + agct[j];//反复删除s的第一个元素，直到s成为S的前缀while(S.substr(0,s.length())!=s){s = s.substr(1);}next[i][j] = s.length();}}for (int i=0;i<n;i++){for (int x=0;x<k;x++){for (int j=0;j<4;j++){int t = next[x][j];if (t==k)continue;dp[i+1][t] = (dp[i+1][t] + dp[i][x]) % MOD;}}}int ans = 0;for (int i=0;i<k;i++)ans = (ans + dp[n][i]) % MOD;cout << ans << endl;}int main(){while(cin>>n>>k>>S){init();solve();}}
只有经历过地狱般的折磨，才有征服天堂的力量。
