hdu 5763 Another Meaning kmp+dp

Arce

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[maxn],match[maxn],dp[maxn],Alen,Blen;
char A[maxn],B[maxn];

inline void up(int & x , int v){
  x += v;
  if(x >= mod) x -= mod;
}

void Build(){
  clr(fail,0);
  fail[0]=fail[1]=0;
  for(int i = 1 ; i < Blen ; ++ i){
    int j = fail[i];
    while( j && B[i] != B[j] ) j=fail[j];
    fail[i + 1] = B[i] == B[j] ? 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[i] != B[j] ) j = fail[j];
      if( A[i] == B[j] ) ++ j;
      if( j == Blen ) match[i - Blen + 1] = 1 , j = fail[j];
    }
    clr(dp,0);
    dp[0]=1;
    for(int i = 0 ; i < Alen ; ++ i){
      up( dp[i + 1] , dp[i] );
      if( match[i] ) up( dp[i + Blen] , dp[i] );
    }
    pf("Case #%d: %d\n",++cas,dp[Alen]);
  }
  return 0;
}