首页 > 代码库 > [HDOJ5763]Another Meaning(KMP, DP)
[HDOJ5763]Another Meaning(KMP, DP)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5763
题意:给定两个字符串a和b,其中a中的字符串如果含有子串b,那么那部分可以被替换成*。问有多少种替换方法。
kmp求出b在a中完全匹配后的结尾位置,然后dp(i)表示匹配到i时替换的方案数(不替换也算一次方案)。首先更新dp(i)=dp(i-1),当且仅当i点是一个完全匹配的终点时,加上dp(i-nb)处的值。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100100; 5 const int mod = 1000000007; 6 int na, nb; 7 char a[maxn]; 8 char b[maxn]; 9 int pre[maxn]; 10 bool vis[maxn]; 11 int dp[maxn]; 12 13 void getpre(char *b, int *pre) { 14 int j, k; 15 pre[0] = -1; 16 j = 0; 17 k = -1; 18 while(j < nb) { 19 if(k == -1 || b[j] == b[k]) { 20 j++; 21 k++; 22 pre[j] = k; 23 if(b[j] != b[k]) pre[j] = k; 24 else pre[j] = pre[k]; 25 } 26 else k = pre[k]; 27 } 28 } 29 30 void kmp() { 31 int i = 0; 32 int j = 0; 33 getpre(b, pre); 34 while(i < na) { 35 if(j == -1 || a[i] == b[j]) { 36 i++; j++; 37 } 38 else j = pre[j]; 39 if(j == nb) vis[i] = 1; 40 } 41 } 42 43 int main() { 44 // freopen("in", "r", stdin); 45 int T, _ = 1; 46 scanf("%d", &T); 47 while(T--) { 48 printf("Case #%d: ", _++); 49 scanf("%s %s", a, b); 50 memset(vis, 0, sizeof(vis)); 51 memset(dp, 0, sizeof(dp)); 52 na = strlen(a); nb = strlen(b); 53 kmp(); dp[0] = 1; 54 for(int i = 1; i <= na; i++) { 55 dp[i] = dp[i-1]; 56 if(vis[i]) { 57 dp[i] += dp[i-nb]; 58 dp[i] %= mod; 59 } 60 } 61 printf("%d\n", dp[na]%mod); 62 } 63 return 0; 64 }
[HDOJ5763]Another Meaning(KMP, DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。