hdu 5763 Another Meaning kmp+dp
Another Meaning题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=5763
Description
As is known to all, in many cases, a word has two meanings. Such as “hehe”, which not only means “hehe”, but also means “excuse me”.
Today, ?? is chating with MeiZi online, MeiZi sends a sentence A to ??. ?? is so smart that he knows the word B in the sentence has two meanings. He wants to know how many kinds of meanings MeiZi can express.
Input
The first line of the input gives the number of test cases T; T test cases follow.
Each test case contains two strings A and B, A means the sentence MeiZi sends to ??, B means the word B which has two menaings. string only contains lowercase letters.
Limits
T <= 30
|A| <= 100000
|B| <= |A|
Output
For each test case, output one line containing “Case #x: y” (without quotes) , where x is the test case number (starting from 1) and y is the number of the different meaning of this sentence may be. Since this number may be quite large, you should output the answer modulo 1000000007
Sample Input
4
hehehe
hehe
woquxizaolehehe
woquxizaole
hehehehe
hehe
owoadiuhzgneninougur
iehiehieh
Sample Output
Case #1: 3
Case #2: 2
Case #3: 5
Case #4: 1
Hint
In the first case, “ hehehe” can have 3 meaings: “he”, “he”, “hehehe”.
In the third case, “hehehehe” can have 5 meaings: “hehe”, “hehe”, “hehe*”, “**”, “hehehehe”.
Hint
题意
给你一个字符串A，给你一个字符串B。
说B这个字符串有两个意思，请问字符串A一共有多少个意思
题解：
DP，dp表示以i结尾有多少种意思，然后用kmp去转移就好了
代码
#include <bits/stdc++.h>
#define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define pb push_back
#define mp make_pair
#define sf scanf
#define pf printf
#define two(x) (1<<(x))
#define clr(x,y) memset((x),(y),sizeof((x)))
#define dbg(x) cout << #x << "=" << x << endl;
const int mod = 1e9 + 7;
int mul(int x,int y){return 1LL*x*y%mod;}
int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
using namespace std;
const int maxn = 1e5 + 15;
int fail,match,dp,Alen,Blen;
char A,B;
inline void up(int & x , int v){
x += v;
if(x >= mod) x -= mod;
}
void Build(){
clr(fail,0);
fail=fail=0;
for(int i = 1 ; i < Blen ; ++ i){
int j = fail;
while( j && B != B ) j=fail;
fail = B == B ? j + 1 : 0;
}
}
int main(int argc,char *argv[]){
int T=read() , cas = 0;
while(T--){
sf("%s%s",A,B);
Alen=strlen(A),Blen=strlen(B);
Build();
clr(match,0);
int j = 0;
for(int i = 0 ; i < Alen ; ++ i){
while( j && A != B ) j = fail;
if( A == B ) ++ j;
if( j == Blen ) match = 1 , j = fail;
}
clr(dp,0);
dp=1;
for(int i = 0 ; i < Alen ; ++ i){
up( dp , dp );
if( match ) up( dp , dp );
}
pf("Case #%d: %d\n",++cas,dp);
}
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15303184/3108598
页:
[1]