poj 3461 Oulipo 向KMP大佬低头~

缘起

曾经使用后缀树&后缀数组（见【2】和【1】）尝试切 poj 3461 Oulipo 但是后缀树直接MLE， 后缀数组被T掉了. 而且关于原因，在【1】和【2】中都做了详细的说明. 没办法，在精确匹配领域，kmp的确是不折不扣的大佬.

向 kmp 大佬低头~ kmp牛逼！

分析

题目见【2】好了. kmp裸题，我就直接上板子了，不懂的童鞋可以参考【3】

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 "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

char s[1000005], t[10005];
int next[10005],n,m;

void makenext()
{
	next[1] = 0;
	for (int i = 2; i<=m+1; i++)
	{
		int k = next[i-1];
		while(k && t[k]!=t[i-1])
		{
			k = next[k];
		}
		next[i] = k+1;
	}
}

void kmp()
{
	int i =1, j=1, ans = 0;
	while(i<=n)
	{
		while(s[i]==t[j] && j<=m && i<=n)
		{
			++i;
			++j;
		}
		if (j==1)
		{
			++i;
		}
		else
		{
			if (j>m)
			{
				ans++;
			}
			j = next[j];
		}
	}
	printf("%d\n", ans);
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%s%s",t+1,s+1);
		m = strlen(t+1);
		n = strlen(s+1);
		makenext();
		kmp();
	}
	return 0;
}

ac情况

Status Accepted
Time 110ms
Memory 1124kB
Length 782
Lang C++
Submitted 2019-10-11 20:52:37
RemoteRunId 20950730

参考

【1】https://yfsyfs.github.io/2019/10/10/poj-3461-Oulipo-%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84/

【2】https://yfsyfs.github.io/2019/10/06/poj-3461-Oulipo-%E5%90%8E%E7%BC%80%E6%A0%91-KMP/

【3】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/