HDU 5763 dp+kmp
Another Meaning
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem 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”, “he*he”, “hehe*”, “**”, “hehehehe”.
标题:テストサンプルをt個あげる テストサンプルごとに2文字列 上の文字列は元の文字列です 次の文字は2番目の意味で置き換えることができます. この言葉にはいくつかの意味がある.
構想:まずkmpでどれだけ重なり合って一致する列があるかを処理して、1つの01列にして、dp[i]を現在のところどれだけの意味があるかを定義して、だから現在一致することができるならば、dp[i]=dp[i-1]+1、現在の列が前の列に影響しないならば、それでは同時に一致することができて、dp[i]=dp[i-1]+dp[i-m]+1で、現在の列が一致しないならば、dp[i]=dp[i-1]で、最後の出力はdp[n-1]+1を出力し、一致するすべての場所が第一の意味であるため、+1を出力する.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem 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”, “he*he”, “hehe*”, “**”, “hehehehe”.
标题:テストサンプルをt個あげる テストサンプルごとに2文字列 上の文字列は元の文字列です 次の文字は2番目の意味で置き換えることができます. この言葉にはいくつかの意味がある.
構想:まずkmpでどれだけ重なり合って一致する列があるかを処理して、1つの01列にして、dp[i]を現在のところどれだけの意味があるかを定義して、だから現在一致することができるならば、dp[i]=dp[i-1]+1、現在の列が前の列に影響しないならば、それでは同時に一致することができて、dp[i]=dp[i-1]+dp[i-m]+1で、現在の列が一致しないならば、dp[i]=dp[i-1]で、最後の出力はdp[n-1]+1を出力し、一致するすべての場所が第一の意味であるため、+1を出力する.
#include
#include
#include
#include
using namespace std;
typedef __int64 ll;
char s1[100005],s2[100005],nex[100005];
ll vis[100005],dp[100005];
int main(){
ll t,i,j,cas=1;
scanf("%I64d",&t);
while(t--){
scanf("%s%s",s1,s2);// s2
memset(nex,-1,sizeof(nex)); // -1
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
ll n=strlen(s1);
ll m=strlen(s2);
j=-1;
for(i=1;i=0&&s2[j+1]!=s2[i])j=nex[j];
if(s2[j+1]==s2[i])j++;
nex[i]=j;
}
j=-1;
for(i=-1;i=0&&s2[j+1]!=s1[i+1])j=nex[j];
if(s2[j+1]==s1[i+1])j++;
if(j==m-1){
//j=next[j]; //
//j=-1; //
j=nex[j];
vis[i+1]=1;
}
}
ll num=0;
for(i=0;i