首页 > 代码库 > HDU 6068 Classic Quotation KMP+DP
HDU 6068 Classic Quotation KMP+DP
Classic Quotation
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.
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.
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.
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
18 5 4iamnotsbiamsb4 73 73 82 7
Sample Output
1100
题意：
给两个字符串只包含小写字母，长度分别为n,m
k个询问，每次询问给出一个L,R
任意的 ( i , j ) ( 1 ≤ i ≤ L , R ≤ j ≤ n ) 删除S串范围(i+1,j-1)内的字符，求出T串在新串内出现的次数总和
题解：
我还是照搬官方题解吧
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;typedef unsigned long long ULL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 6e4+10, M = 2e2+20,inf = 2e9;int zfail[N],ffail[N];LL dp[N][M],f[N][M],sumdp[N][M],sumf[N][M],dp2[N][M],f2[N][M];char a[N],b[N];int n,m,k,T;LL solve(int ll,int rr) { LL ret = 0; ret += 1LL * sumdp[ll][m] * (n - rr + 1) + 1LL * sumf[rr][1] * (ll); for(int i = 1; i < m; ++i) { ret += 1LL*dp2[ll][i] * f2[rr][i+1]; } return ret;}void init() { for(int j = 0; j <= m+1; ++j) zfail[j] = 0,ffail[j] = m+1; for(int i = 0; i <= n+1; ++i) for(int j = 0; j <= m+1; ++j) dp[i][j] = 0,f[i][j] = 0,sumdp[i][j] = 0,sumf[i][j] = 0; int j = 0; for(int i = 2; i <= m; ++i) { while(j&&b[j+1]!=b[i]) j = zfail[j]; if(b[j+1] == b[i]) j++; zfail[i] = j; } j = m+1; for(int i = m-1; i >= 1; --i) { while(j<=m&&b[j-1]!=b[i]) j = ffail[j]; if(b[j-1] == b[i]) j--; ffail[i] = j; } j = 0; for(int i = 1; i <= n; ++i) { while(j&&a[i]!=b[j+1]) j = zfail[j]; if(b[j+1] == a[i]) j++; dp[i][j] += 1; } j = m+1; for(int i = n; i >= 1; --i) { while(j<=m&&b[j-1]!=a[i]) j = ffail[j]; if(b[j-1] == a[i]) j--; f[i][j] += 1; } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { dp[i][j] += dp[i-1][j]; sumdp[i][j] += sumdp[i-1][j]+dp[i][j]; } } for(int i = n; i >= 1; --i) { for(int j = m; j >= 1; --j) { f[i][j] += f[i+1][j]; sumf[i][j] += sumf[i+1][j]+f[i][j]; } }}void init2() { for(int i = 0; i <= n+1; ++i) for(int j = 0; j <= m+1; ++j) dp2[i][j] = 0,f2[i][j] = 0; for(int i = 0; i <= n+1; ++i) dp2[i][0] = 1,f2[i][m+1] = 1; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { if(a[i] == b[j] && dp2[i-1][j-1]) dp2[i][j] = 1; } } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { dp2[i][j] += dp2[i-1][j]; } } for(int i = n; i >= 1; --i) { for(int j = m; j >= 1; --j) { if(a[i] == b[j] && f2[i+1][j+1]) f2[i][j] = 1; } } for(int i = n; i >= 1; --i) { for(int j = m; j >= 1; --j) { f2[i][j] += f2[i+1][j]; } }}int main() { scanf("%d",&T); while(T--) { scanf("%d%d%d%s%s",&n,&m,&k,a+1,b+1); init(); init2(); while(k--) { int L,R; scanf("%d%d",&L,&R); printf("%lld\n",solve(L,R)); } } return 0;}
HDU 6068 Classic Quotation KMP+DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。