HDU 2594 Simpsons’ Hidden Talents

Posted on | Edited on

题意

求出最大的k使s1长度为k的前缀等于s2长度为k的后缀 ## 题解 扩展KMP模版题，求出extend之后，从前往后枚举位置i，只要往后extend[i]能到末尾就输出答案 ## 代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>

char s[100000], t[100000];
int n, m;
int nextx[100000], extend[100000];
int ans;

void getnextx()
{
	int pos = -1, last = -1;
	for (int i = 2; i <= m; i++)
	{
		int k = (pos == -1 || i > last) ? 0 : std::min(nextx[i - pos + 1], last - i + 1);
		while (k + 1 <= n && t[i + k] == t[k + 1])
		{
			k++;
		}
		nextx[i] = k;
		if (i + nextx[i] - 1 > last)
		{
			pos = i;
			last = i + nextx[i] - 1;
		}
	}
}

int main()
{
	while (scanf("%s%s", s + 1, t + 1) == 2)
	{
		n = strlen(s + 1);
		m = strlen(t + 1);
		getnextx();
		int pos = -1, last = -1;
		for (int i = 1; i <= m; i++)
		{
			int k = (pos == -1 || i > last) ? 0 : std::min(nextx[i - pos + 1], last - i + 1);
			while (k + 1 <= n && i + k <= m && t[i + k] == s[k + 1])
			{
				k++;
			}
			extend[i] = k;
			if (i + extend[i] - 1 > last)
			{
				pos = i;
				last = i + extend[i] - 1;
			}
		}
		ans = 0;
		for (int i = 1; i <= m; i++)
		{
			if (i + extend[i] - 1 == m)
			{
				ans = extend[i];
				break;
			}
		}
		if (ans)
		{
			for (int i = 1; i <= ans; i++)
			{
				printf("%c", s[i]);
			}
			printf(" ");
		}
		printf("%d\n", ans);
	}
	return 0;
}