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,⋯,bm
is 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
复制代码
1
2
3
4
5
6
7
8
9
10
112 6 3 1 1 2 3 1 2 3 1 2 3 6 3 2 1 3 2 2 3 1 1 2 3
Sample Output
复制代码
1
2
3
4
5
6Case #1: 2 Case #2: 1
将a数列的元素按照对p取模的值重新排列,构成新的数列,不同取模值之间加上一个-1作为分界
然后直接跑KMP即可
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83#include<cstdio> #include<string> #include<cstring> using namespace std; int a[200001],aa[100001],b[100001]; int loc[100001],net[100001]; int n,m; inline void KMP() { int i,j; for(i=1;i<m;i++) { j=i; while(j>0) { j=net[j]; if(b[j]==b[i]) { net[i+1]=j+1; break; } } } for(i=0,j=0;i<n;i++) { if(j<m&&a[i]==b[j]) j++; else { while(j>0) { j=net[j]; if(a[i]==b[j]) { j++; break; } } } if(j==m) { loc[0]++; loc[loc[0]]=(i-m+1)+1; } } } int main() { int T,k=0; scanf("%d",&T); while(T>0) { T--; k++; int p; scanf("%d%d%d",&n,&m,&p); int i,j; for(i=0;i<n;i++) scanf("%d",&aa[i]); for(i=0;i<m;i++) scanf("%d",&b[i]); int tot=-1; for(i=0;i<p;i++) { for(j=i;j<n;j+=p) { tot++; a[tot]=aa[j]; } tot++; a[tot]=-1; } // for(i=0;i<=tot;i++) // printf("%d ",a[i]); // printf("n"); memset(net,0,sizeof(net)); loc[0]=0; n=tot+1; KMP(); printf("Case #%d: %dn",k,loc[0]); } return 0; }
最后
以上就是大意山水最近收集整理的关于hdu 5918 Harmonic Value Description 2016ACM/CCPC长春赛区现场赛H的全部内容,更多相关hdu内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复