本文主要是介绍Codeforces Round #282 (Div. 1) B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
B. Obsessive String
题意：给两个字符串s和t。你需要在s里面取出一些不互相重叠的子串，使得每一个子串都包含t，问有多少种取法。
思路：字符串hash+dp。hash是为了高效比较s的子串和t是否相等。设s长度为n，递推计算s1~si的结果，i=1...n。不好用语言描述，见代码。。。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;const int maxn=100010;
const int mod=1e9+7;#define ull unsigned long long char s[maxn];
char t[maxn];const ull x=123;
ull xn[maxn];
ull H[maxn];
ull hash[maxn];int sum[maxn]; //每个长度结果的前缀和
int dp[maxn]; //int main(){scanf("%s",s+1);scanf("%s",t+1);int n=strlen(s+1);int m=strlen(t+1);//计算字符串哈希 xn[0]=1;for(int i=1;i<n;i++){xn[i]=xn[i-1]*x;}H[n]=0;for(int i=n;i>0;i--){H[i]=H[i+1]*x+s[i]-'a';}ull hash_t=0;for(int i=m;i>0;i--){hash_t*=x;hash_t+=t[i]-'a';}for(int i=1;i<=n-m+1;i++){hash[i]=H[i]-xn[m]*H[i+m];}int tmp=0; //tmp是串s长度增加1时，结果增加的量 for(int i=m;i<=n;i++){if(hash[i-m+1]==hash_t){ //匹配的时候更新tmp的值 tmp=(sum[i-m]+i-m+1)%mod; //这一行是重点，计算串s添加上s[i]时，结果会增加多少 }dp[i]=(dp[i-1]+tmp)%mod; //递推结果 sum[i]=(sum[i-1]+dp[i])%mod; //计算前缀和 }cout<<dp[n]<<endl;return 0;
}
这篇关于Codeforces Round #282 (Div. 1) B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
