首页 > 代码库 > Codeforces Round #282 Div.1 B Obsessive String --DP
Codeforces Round #282 Div.1 B Obsessive String --DP
题意： 给两个串S,T，问能找出多少的S的(a1,b1)(a2,b2)..(ak,bk)，使Sa1---Sb1,...Sak---Sbk都包含子串T，其中k>=1,且(a1,b1)...(ak,bk)互不相交。
比如S = "abacaba",T="aba", 当k=1时，(0,6)满足，还有其他只包含一个aba串的也满足，k-2时，(0,2)(3,6)满足，(0,2)(4,6)也满足，(0,3)(4,6)也满足，所以总共有12种。
解法：dp.先用kmp找出所有匹配点。
定义dp[i] = bn为 i 的方法数(尾部为 i )。
则转移方程： 如果 i 是某匹配的尾字母时，
左边意味着取的区间数K>1的情况，第一个循环枚举ak,第二个循环枚举b(k-1)， 右边意味着取得区间数为1，即就取一个区间的方式数（为从左边取起，取到此时匹配串的第一个字母为止）
否则 dp[i] = dp[i-1]
于是，我们可以维护 
, 再维护
那么sum[i] = sum[i-1]+ans[i], ans[i] = ans[i-1]+dp[i];
（感谢God yue 提供思路）
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define Mod 1000000007#define lll __int64using namespace std;#define N 100007char S[N],T[N];int next[N],flag[N],n,m;void getnext(char* b) { int i = 0,j = next[0] = -1; while(i < m) { if(j == -1 || b[i] == b[j]) next[++i] = ++j; else j = next[j]; }}void kmp(char* a,char *b){ memset(flag,0,sizeof(flag)); int i = -1,j = -1; while(i < n && j < m) { if(j == -1 || a[i] == b[j]) i++,j++; else j = next[j]; if(j == m) { flag[i] = 1; j = next[j]; } }}lll dp[N],ans[N],sum[N];int main(){ int i,j; scanf("%s%s",S,T); n = strlen(S), m = strlen(T); getnext(T); kmp(S,T); dp[0] = ans[0] = sum[0] = 0; for(i=1;i<=n;i++) { if(!flag[i]) dp[i] = dp[i-1]; else dp[i] = (sum[i-m]+i-m+1)%Mod; ans[i] = (ans[i-1] + dp[i])%Mod; sum[i] = (sum[i-1] + ans[i])%Mod; } cout<<ans[n]<<endl; return 0;}
Codeforces Round #282 Div.1 B Obsessive String --DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。