(KMP 1.1)hdu 1711 Number Sequence(KMPの簡単な応用--patternがtextの中で初めて現れる位置を求める)

タイトル:
Number Sequence
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 12902    Accepted Submission(s): 5845
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
   
   
   
   

 
Source
HDU 2007-Spring Programming Contest
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   1358  3336  1686  3746  2222 
テーマ分析:
               KMP.簡単な問題.
コードは次のとおりです.

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

const int maxn = 1000001;

int n;//      
int m;//      

int text[maxn];//   
int pattern[maxn];//   
int nnext[maxn];//next  .   next            

/*O(m)    next  */
void get_next() {
	nnext[0] = nnext[1] = 0;
	for (int i = 1; i < m; i++) {
		int j = nnext[i];
		while (j && pattern[i] != pattern[j])
			j = nnext[j];
		nnext[i + 1] = pattern[i] == pattern[j] ? j + 1 : 0;
	}
}

/*o(n)       
 *
 *           
 */
int kmp() {
	int j = 0;/*             */
	for (int i = 0; i < n; i++) {/*       */
		while (j && pattern[j] != text[i])/*      ，      ，       j = 0*/
			j = nnext[j];
		if (pattern[j] == text[i])/*             */
			j++;
		if (j == m) {/*         */
//         printf("%d
" , i-m+2);/*               ，    */
			return i - m + 2;//      1   
		}
	}
//    printf("-1
");

	return -1; //           
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		int i;
		for (i = 0; i < n; ++i) {
			scanf("%d", &text[i]);
		}

		for (i = 0; i < m; ++i) {
			scanf("%d", &pattern[i]);
		}

		get_next();
		printf("%d
", kmp());
	}

	return 0;
}