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 |
#include <stdio.h>#include <string.h>int a[1000005],b[10005];int next[10005];int n,m,t;void
getNext(){ int
j,i; j=0; i=-1; next[0]=-1; while(j<m-1) { if(i==-1||b[i]==b[j]) { j++; i++; next[j]=i; } else
i=next[i]; }}int
KMPMatch(){ int
i,j; j=0; i=0; while(i<n&&j<m) { if(j==-1||a[i]==b[j]) { j++; i++; } else
j=next[j]; } if(j>=m) return
i-m+1; else
return -1;}int
main(){ int
i,j; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0;i<n;i++) { scanf("%d",&a[i]); } for(i=0;i<m;i++) { scanf("%d",&b[i]); } getNext(); printf("%d\n",KMPMatch()); } return
0;} |
hdu 1711 Number Sequence（KMP）,布布扣,bubuko.com
原文：http://www.cnblogs.com/ccccnzb/p/3575246.html