hdu 1711( 模式串T在主串S中首次出现的位置)

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 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 
 6 
 7 int Next[10010];
 8 int S[1000010], T[10010];  //题目中为数字串 
 9 int slen, tlen;
10 
11 void getNext()
12 {
13     int j, k;
14     j = 0; k = -1; Next[0] = -1;
15     while(j < tlen)
16         if(k == -1 || T[j] == T[k])
17             Next[++j] = ++k;
18         else
19             k = Next[k];
20 
21 }
22 
23 /*
24 返回模式串T在主串S中首次出现的位置
25 返回的位置是从1开始的。
26 */
27 int KMP_Index()
28 {
29     int i = 0, j = 0;
30     getNext();
31 
32     while(i < slen && j < tlen)
33     {
34         if(j == -1 || S[i] == T[j])
35         {
36             i++; j++;
37         }
38         else
39             j = Next[j];
40     }
41     if(j == tlen)
42         return i - tlen + 1;
43     else
44         return -1;
45 }
46 int main()
47 {
48     
49     int TT;
50     int i, cc;
51     scanf("%d",&TT);
52     while(TT--)
53     {
54         scanf("%d %d" ,&slen , &tlen);
55         for (i = 0 ;i < slen ; i++)
56            scanf("%d" , &S[i]) ;
57         for (i = 0 ;i < tlen ; i++)
58            scanf("%d" , &T[i]) ;
59         
60         printf("%d
" , KMP_Index()) ;
61         
62     }
63     return 0;
64 }

View Code