51nod 1286 三段子串

Posted on

题意

给定一个字符串S，找到另外一个字符串T，T既是S的前缀，也是S的后缀，并且在中间某个地方也出现一次，并且这三次出现不重合。求T最长的长度。 ## 题解 跑一遍KMP和扩展KMP，然后从大到小枚举所有的T使T是S的前缀和后缀，然后维护一段区间的extend的最大值，由于T是从大到小枚举的，所以区间是从小到大的。时间复杂度$ O(n) $ ## 代码

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
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstring>
#include <algorithm>

int n;
char s[2000000];
int fail[2000000], nextx[2000000];

void getfail()
{
	int j = 0;
	for (int i = 2; i <= n; i++)
	{
		while (j && s[j + 1] != s[i])
		{
			j = fail[j];
		}
		if (s[j + 1] == s[i])
		{
			j++;
		}
		fail[i] = j;
	}
}

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

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	getfail();
	getnextx();
	int maxx = 0;
	int k = fail[n];
	for (; k * 3 > n; k = fail[k]);
	int l = k + 1;
	int r = n - 2 * k + 1;
	for (int i = l; i <= r; i++)
	{
		maxx = std::max(maxx, nextx[i]);
	}
	if (maxx >= k)
	{
		printf("%d\n", k);
		return 0;
	}
	for (k = fail[k]; k; k = fail[k])
	{
		int ll = k + 1;
		int rr = n - 2 * k + 1;
		for (int i = ll; i < l; i++)
		{
			maxx = std::max(maxx, nextx[i]);
		}
		for (int i = r + 1; i <= rr; i++)
		{
			maxx = std::max(maxx, nextx[i]);
		}
		l = ll;
		r = rr;
		if (maxx >= k)
		{
			printf("%d\n", k);
			return 0;
		}
	}
	printf("0\n");
	return 0;
}