首页 > > 程序设计 > C/C++ >

hdu 6068--Classic Quotation（kmp+DP）

2018-06-17 21:56:44来源：未知阅读 ()

题目链接

Problem Description

When online chatting, we can save what somebody said to form his ''Classic Quotation''. Little Q does this, too. What's more? He even changes the original words. Formally, we can assume what somebody said as a string

Input

The first line of the input contains an integer

Output

For each question, print a single line containing an integer, denoting the answer.

Sample Input

8 5 4

iamnotsb

iamsb

4 7

3 7

3 8

2 7

Sample Output

题意：有小写字符串s和t，现在在s中去掉连续子串后，剩余s[1…i] 和 s[j…n] 连在一起构成一个新s串，计算t串在新s串中出现了几次。现在q次询问，每次输入L和R，去掉连续子串后s[1…i]和s[j...n]拼接成新串s，1<=i<=L && R<=j<=n,求t串在这些新串中出现的次数和？

思路：

代码如下:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=50005;
char s[N],t[105];
int pre[N],num[N][105];
int suf[N][105];
int next1[105];
int next2[105][30],flag[105][30];
int n,m,q;

void KMP()
{
    next1[0]=0;
    for(int i=1,k=0; i<m; ++i)
    {
        while(k>0 && t[i]!=t[k]) k=next1[k-1];
        if(t[i]==t[k]) k++;
        next1[i]=k;
    }
}

void cal()
{
    memset(flag,0,sizeof(flag));
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<26;j++)
        {
            char x=j+'a';
            int k=i;
            while(k>0 && t[k]!=x) k=next1[k-1];
            if(t[k]==x) k++;
            next2[i][j]=k;
            if(k==m) flag[i][j]=1,next2[i][j]=next1[m-1];
        }
    }

    memset(pre,0,sizeof(pre));
    memset(num,0,sizeof(num));
    for(int i=0,k=0;i<n;i++)
    {
        while(k>0&&t[k]!=s[i]) k=next1[k-1];
        if(t[k]==s[i]) k++;
        if(k==m) pre[i]++,num[i][next1[m-1]]=1;
        else num[i][k]=1;
        pre[i]+=pre[i-1];
    }
    for(int i=1;i<n;i++)
        for(int j=0;j<m;j++)
            num[i][j]+=num[i-1][j];
    for(int i=1;i<n;i++) pre[i]+=pre[i-1];///前缀和;

    memset(suf,0,sizeof(suf));
    for(int i=n-1;i>=0;i--)
    {
        int x=s[i]-'a';
        for(int j=0;j<m;j++)
            suf[i][j]=flag[j][x]+suf[i+1][next2[j][x]];
    }
    for(int j=0;j<m;j++) ///后缀和;
       for(int i=n-1;i>=0;i--)
          suf[i][j]+=suf[i+1][j];
}

int main()
{
    int T; cin>>T;
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&q);
        scanf("%s%s",s,t);
        KMP();
        cal();
        while(q--)
        {
            int L,R; scanf("%d%d",&L,&R);
            LL ans=(LL)pre[L-1]*(LL)(n-R+1);
            for(int i=0;i<m;i++)
            {
                ans+=(LL)num[L-1][i]*(LL)suf[R-1][i];
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}
/**
2342
8 3 3463
abcababc
abc
8 3 234
aabbcccbbb
aaabb

4
10 3 23
ababcababc
aba
3 5
*/