首页 > 代码库 > HDU 5918 Sequence I KMP
HDU 5918 Sequence I KMP
Sequence I
Problem Description
Mr. Frog has two sequences a1,a2,?,an and b1,b2,?,bm and a number p. He wants to know the number of positions q such that sequence b1,b2,?,bmis exactly the sequence aq,aq+p,aq+2p,?,aq+(m−1)p where q+(m−1)p≤n and q≥1.
Input
The first line contains only one integer T≤100, which indicates the number of test cases.
Each test case contains three lines.
The first line contains three space-separated integers 1≤n≤106,1≤m≤106 and 1≤p≤106.
The second line contains n integers a1,a2,?,an(1≤ai≤109).
the third line contains m integers b1,b2,?,bm(1≤bi≤109).
Each test case contains three lines.
The first line contains three space-separated integers 1≤n≤106,1≤m≤106 and 1≤p≤106.
The second line contains n integers a1,a2,?,an(1≤ai≤109).
the third line contains m integers b1,b2,?,bm(1≤bi≤109).
Output
For each test case, output one line “Case #x: y”, where x is the case number (starting from 1) and y is the number of valid q’s.
Sample Input
26 3 11 2 3 1 2 31 2 36 3 21 3 2 2 3 11 2 3
Sample Output
Case #1: 2Case #2: 1
题意:
给你a,b两个序列
和一个p ,求有多少个 q恰好满足 b1,b2,b3....bm 就是 a[q],a[q+p],a[q+2p]......a[q+(m-1)p];
题解:
将a序列,每隔p位置分成一组,这样最多有p组,个数和是n
将每组和b序列跑KMP计算答案
#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;const long long INF = 1e18;const double Pi = acos(-1.0);const int N = 1e6+10, M = 1e6, mod = 1e9+7, inf = 2e9;int T,n,m,p,s[N],t[N],ans = 0;vector<int > P[N];int nex[N];int main(){ int cas = 1; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&p); for(int i = 1; i <= n; ++i) scanf("%d",&t[i]); for(int i = 1; i <= m; ++i) scanf("%d",&s[i]); for(int i = 0; i < p; ++i) P[i].clear(); memset(nex,0,sizeof(nex)); ans = 0; int k = 0; for(int i=2; i<=m; i++) { while(k>0&&s[k+1]!=s[i]) k = nex[k]; if(s[k+1]==s[i])k++; nex[i] = k; } if(p == 1) { k = 0; for(int i=1; i<=n; i++) { while(k>0&&s[k+1]!=t[i]) k = nex[k]; if(s[k+1]==t[i]) k++; if(k==m) { k = nex[k]; ans++; } } printf("Case #%d: ",cas++); printf("%d\n",ans); } else { for(int i = 1; i <= n; ++i) P[i % p].push_back(t[i]); for(int i = 0; i < p; ++i) { k = 0; for(int j = 0; j < P[i].size(); ++j) { while(k>0&&s[k+1]!=P[i][j]) k = nex[k]; if(s[k+1]==P[i][j]) k++; if(k==m) { k = nex[k]; ans++; } } } printf("Case #%d: ",cas++); printf("%d\n",ans); } }}
HDU 5918 Sequence I KMP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。