(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\n" , i-m+2);/*输出在文本串中第一个匹配的位置，不是下标*/
			return i - m + 2;//返回的位置从1开始算
		}
	}
//    printf("-1\n");

	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\n", kmp());
	}

	return 0;
}