扩展KMP算法 hdu 2594 Simpsons’ Hidden Talents

缘起

【1】中我们通过严格的数学推导引入了扩展KMP算法. 自然需要一块板子来试试【1】中写的算法有没有漏洞. 于是找到了 hdu2594

分析

题意如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给你2个字符串T和p（长度都不会超过5w），要你求出最大的k,使得prefix(T,k)=suffix(p,k), 即T的前缀=p的后缀
求出k以及相应的前（后）缀， 如果不存在，就输出0了事. 

样例输入

clinton
homer
riemann
marjorie

样例输出

0
rie 3

限制:
Time limit1000 ms
Memory limit32768 kB

显然是扩展KMP裸题. 就是在线性时间内求出extend数组即可.

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
79
80
//#include "stdafx.h"
#include <iostream>
#include <cstring>
//#define LOCAL
using namespace std;

const int MAX_N = 50005;

char T[MAX_N], p[MAX_N];

int n,m, extend[MAX_N], pnext[MAX_N];

void makenext()
{
	int k = 1;
	while(p[k]==p[k+1]) k++;
	pnext[2] = k-1;
	int a = 2,spread = a+pnext[a]-1;
	for (k=2; k<m; k++)
	{
		if (k+pnext[k-a+2]<spread) pnext[k+1] = pnext[k-a+2];
		else
		{
			int x = spread+1, y = spread+1-k; 
			if (x<k+1) x = k+1; 
			if (!y) y = 1;
			while (p[x]&&p[y]&&p[x]==p[y]) x++,y++;
			pnext[k+1] = x-1-k;
			if (x-1>spread) spread = x-1, a=k+1;
		}
	}
}

void exkmp()
{
	int k=1,j=1;
	while(T[k]&&p[j]&&T[k] == p[j])k++,j++;
	extend[1] = k-1;
	int a = 1, spread = k-1, lcp = 0;
	if (extend[1]==n)
	{
		printf("%s %d\n", T+1, n);
		return;
	}
	for(k = 1; k<n; k++)
	{
		if (pnext[k-a+2]+k<spread) extend[k+1]=pnext[k-a+2];
		else
		{
			int x = spread+1,y=spread+1-k;
			if (x<k+1) x = k+1;
			if (!y) y = 1;
			while(T[x]&&p[y]&&T[x]&&T[x] == p[y])x++,y++;
			extend[k+1]=x-1-k;
			if (x-1>spread) spread = x-1,a=k+1; // 更新
		}
		if (extend[k+1]==n-k&&extend[k+1]>lcp) // T的后缀等于p的前缀
		{
			lcp = extend[k+1];
		}
	}
	lcp?printf("%s %d\n", T+n-lcp+1, lcp):printf("%d\n",lcp);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif

	while(~scanf("%s%s", p+1, T+1))
	{
		n = strlen(T+1);
		m = strlen(p+1);
		makenext();
		exkmp();
	}
	return 0;
}

ac情况

Status Accepted
Time 15ms
Memory 2220kB
Length 1431
Lang C++
Submitted 2019-07-07 21:52:28
Shared
RemoteRunId 29576328

比较快了

参考

【1】https://yfsyfs.github.io/2019/07/07/%E6%89%A9%E5%B1%95KMP%E9%97%AE%E9%A2%98/