hdu 1711 Number Sequence KMP模板题

缘起

【1】中按照自己的分析写出了kmp的板子，自然想测一下板子的性能. hdu 1711 来练手

不熟悉kmp的童鞋可以参考【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
【题意】

给出两个数字序列：a [1]，a [2]，......，a [N]和b [1]，b [2]，......，b [M] （1 <= M <= 10000,1 <= N <= 1000000）。 你的任务是找到一个数字K，它使a[K] = b [1]，a[K + 1] = b [2]，......，a [K + M  -  1] = b [M]。 如果存在多个K，则输出最小的K.

【输入】
第一行输入是数字T，表示案例数。 每个案例包含三行。 第一行是两个数字N和M（1 <= M <= 10000,1 <= N <= 1000000）。 第二行包含N个整数，表示[1]，a [2]，......，a [N]。 第三行包含M个整数，表示b [1]，b [2]，......，b [M]。 所有整数都在[-1000000,1000000]的范围内。

【输出】

对于每个测试用例，您应输出一行仅包含上述K的行。 如果不存在这样的K，则输出-1。

【样例输入】

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

【样例输出】
6
-1

【要求】
Time limit		5000 ms
Memory limit	32768 kB

显然，a是text, b是pattern（不知道这种术语的，参见【1】）. 如果用BF算法的话，复杂度是O(1w*100w)=O(100亿) 这显然不是5秒内可以完成的任务。 所以需要使用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
66
67
68
69
70
71
72
73
74
75
76
77
78
#include "stdafx.h"
#include <iostream>
#include <cstring>
using namespace std;
#define LOCAL

const int MAX_N = 1000000+5;

int text[MAX_N], p[MAX_N];
int pnext[MAX_N];

void makenext()
{
	pnext[1] = 0;
	for (int j = 2; j<= p[0]+1;j++)
	{
		int k = pnext[j-1];
		while(k&&p[j-1]!=p[k])
		{
			k = pnext[k];
		}
		pnext[j] = k+1;
	}
}

void kmp()
{
	int i = 1, j=1; 
	while(i<=text[0]) 
	{
		while (text[i] == p[j] && j<=p[0] && i<=text[0])
		{
			i++;
			j++;
		}
		if (j==1) 
		{
			i++;
		}
		else
		{
			if (j>p[0]) 
			{
				printf("%d\n", i-p[0]);
				return;
			}
			j = pnext[j];
		}
	}
	puts("-1");
}



int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t,n,m;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &n,&m);
		text[0] = n;
		p[0] = m;
		for (int i = 1; i<=n; scanf("%d", text+(i++)));
		for (int i = 1; i<=m; scanf("%d", p+(i++)));
		makenext();
		kmp();
	}
	return 0;
}
/*
测试数据
GooglGoogle
Google
*/

ac情况

Status Accepted
Time 920ms
Memory 5748kB
Length 949
Lang C++
Submitted 2019-06-22 18:11:38
Shared
RemoteRunId 29467731

要求是5秒，但是我不到1秒就完成了任务，可见kmp算法之快!!!

参考

【1】https://yfsyfs.github.io/2019/06/17/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95%E4%B9%8Bkmp/