hdu 6068–Classic Quotation(kmp+DP),hdu6068–classic

题目链接

 

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 S whose length
is n. He will choose a continuous substring
of S(or choose nothing), and remove it,
then merge the remain parts into a complete one without changing order,
marked as S′. For example, he might
remove ”not” from the string ”I am not SB.”, so that the new
string S′ will be ”I am SB.”,
which makes it funnier.

威尼斯人平台 1

有小写字符串s和t。After doing lots of such things, Little Q finds out that string T occurs as a continuous substring
of S′ very often.

Now given strings S and T, Little Q has k questions. Each question is,
given L and R, Little Q will remove a substring so
that the remain parts are S[1..i] and S[j..n],
what is the expected times that T occurs as a
continuous substring of S′ if he choose every
possible pair of (i,j)(1≤i≤L,R≤j≤n) equiprobably?
Your task is to find the answer E, and report E×L×(n−R+1) to
him.

Note : When counting occurrences, T can overlap with each
other.
 

 

Input The first line of the input contains an integer C(1≤C≤15),
denoting the number of test cases.

In each test case, there are 3 integers n,m,k(1≤n≤50000,1≤m≤100,1≤k≤50000) in
the first line, denoting the length of S, the length of T and the number of questions.

In the next line, there is a string S consists of n lower-case English letters.

威尼斯人平台,Then in the next line, there is a string T consists of m lower-case English letters.

In the following k lines, there are 2 integers L,R(1≤L<R≤n) in
each line, denoting a
question.
 

 

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

 

Sample Input 1 8 5 4 iamnotsb iamsb 4 7 3 7 3 8 2 7  

 

Sample Output 1 1 0 0    
题意:有小写字符串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串在这些新串中出现的次数和?   思路:        
  威尼斯人平台 2    
代码如下:

#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("%lldn",ans);
        }
    }
    return 0;
}
/**
2342
8 3 3463
abcababc
abc
8 3 234
aabbcccbbb
aaabb

4
10 3 23
ababcababc
aba
3 5
*/

 

6068–Classic
Quotation(kmp+DP),hdu6068–classic 题目链接 Problem Description When
online chatting, we can save what somebody said to form his ”Classic
Quotation”….

相关文章