## 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. 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?
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.

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,

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

Sample Output 1 1 0 0

s[j…n]

&& 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;
int pre[N],num[N];
int suf[N];
int next1;
int next2,flag;
int n,m,q;

void KMP()
{
next1=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”….