hdu-5763 Another Meaning(kmp+dp) Another Meaning

hdu-5763 Another Meaning(kmp+dp)
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

hehehe

hehe

woquxizaolehehe

woquxizaole

hehehehe

hehe

owoadiuhzgneninougur

iehiehieh

Sample Output

Case #1: 3

Case #2: 2

Case #3: 5

Case #4: 1

题意：

给了一个单词它有两种意思,现在有一个字符串.问你这个字符串有多少种不同的意思;

思路：

设dp[i]表示[1,i]这段字符串的意思总数,考虑以i位结尾的的这一小段是否和单词匹配;

如果匹配,dp[i]=dp[i-1]+dp[i-strlen(B)];不匹配的话dp[i]=dp[i-1];

然后就是kmp找出所有的匹配位置的结点flag[i]标记下来;

AC代码:

/************************************************ 
┆  ┏┓　　　┏┓ ┆    
┆┏┛┻━━━┛┻┓ ┆ 
┆┃　　　　　　　┃ ┆ 
┆┃　　　━　　　┃ ┆ 
┆┃　┳┛　┗┳　┃ ┆ 
┆┃　　　　　　　┃ ┆  
┆┃　　　┻　　　┃ ┆ 
┆┗━┓　  　┏━┛ ┆ 
┆　　┃　  　┃　　┆　　　　　　 
┆　　┃　  　┗━━━┓ ┆ 
┆　　┃　 AC代马 　　┣┓┆ 
┆　　┃　        　　┏┛┆ 
┆　　┗┓┓┏━┳┓┏┛ ┆ 
┆　　　┃┫┫　┃┫┫ ┆ 
┆　　　┗┻┛　┗┻┛ ┆       
************************************************ */  


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>

using namespace std;

#define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef  long long LL;

template<class T> void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
    F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
    if(!p) { puts("0"); return; }
    while(p) stk[++ tp] = p%10, p/=10;
    while(tp) putchar(stk[tp--] + '0');
    putchar('
');
}

const LL mod=1e9+7;
const double PI=acos(-1.0);
const int inf=1e9;
const int N=1e5+100;
const int maxn=(1<<8);
const double eps=1e-8;

char A[N],B[N];
int nex[N],flag[N];
LL dp[N];

inline void makenext()
{
    int k = -1,j = 0,len = strlen(B);
    nex[0] = -1;
    while(j < len)
    {
        if(k == -1||B[j] == B[k])
        {
            j++;
            k++;
            nex[j] = k;//相等的话就往后继续;
        }
        else k = nex[k];//不等的话就相当于kmp一样,把模式串的这个子串用已经求出来的next跳转;
    }
}
inline void kmp()
{
    mst(flag,0);
    makenext();
    int posP = 0,posT = 0;
    int lenP = strlen(B),lenT = strlen(A);
    while(posP < lenP&&posT < lenT)
    {
        if(posP == -1||B[posP] == A[posT])
        {
            posP++;
            posT++;
        }
        else posP = nex[posP];
        if(posP == lenP)
        {
            flag[posT-1]=1;
            posP=nex[posP];
        }
    }
}

int main()
{       
        int t,Case=0;
        read(t);
        while(t--)
        {
            scanf("%s",A);
            scanf("%s",B);
            kmp();
            int len=strlen(A),l=strlen(B);
            dp[0]=1;
            For(i,1,len)
            {
                if(!flag[i-1])dp[i]=dp[i-1];
                else dp[i]=(dp[i-1]+dp[i-l])%mod;
            }
            printf("Case #%d: %lld
",++Case,dp[len]);
        }
        return 0;
}

hdu-5763 Another Meaning(kmp+dp) Another Meaning

相关推荐