作者:哦呦喂酿 | 来源:互联网 | 2023-05-30 15:44
KMP模板题,做了一天,泪奔啊~~~ProblemDescriptionGiventwosequencesofnumbers:a[1],a[2],,a[N],and
KMP模板题,做了一天,泪奔啊~~~
Problem Description
Given two sequences of numbers : a[1], a[2], ...... ,
a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <=
1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] =
b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output
the smallest one.
Input
The first line of input is a number T which indicate
the number of cases. Each case contains three lines. The first line is two
numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second
line contains N integers which indicate a[1], a[2], ...... , a[N]. The third
line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers
are in the range of [-1000000, 1000000].
Output
For each test case, you should output one line which
only contain K described above. If no such K exists, output -1 instead.
Sample Input
2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1
Sample Output
6
-1
?
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 #include int a[1000005],b[10005]; int next[10005]; int n,m,t; void
getNext() class="line number9 index8 alt2">{ int
j,i; j=0; i=-1; next[0]=-1; while (j { if (i==-1||b[i]==b[j]) { j++; i++; next[j]=i; } else
i=next[i]; } class="line number24 index23 alt1">} int
KMPMatch() class="line number28 index27 alt1">{ int
i,j; j=0; i=0; while (i { if (j==-1||a[i]==b[j]) { j++; i++; } else
j=next[j]; } if (j>=m) return
i-m+1; else
return -1; class="line number45 index44 alt2">} int
main() class="line number47 index46 alt2">{ int
i,j; scanf ( "%d" ,&t); while (t--) { scanf ( "%d%d" ,&n,&m); for (i=0;i { scanf ( "%d" ,&a[i]); } for (i=0;i { scanf ( "%d" ,&b[i]); } getNext(); printf ( "%d\n" ,KMPMatch()); } return
0; class="line number65 index64 alt2">} |
hdu 1711 Number Sequence(KMP),布布扣,bubuko.com