
计蒜客 – 匹配格式
有一字符串 S,蒜头君想在 S 中找到最长的子串 E,使得 S 满足格式 “EAEBE”,其中 A, B 可以为任意的 S 子串。也就是说子串 E 既是 S 的前缀也是 S 的后缀,同时还在 S 中间出现,但不与前缀 E 与后缀 E 重叠。
输入格式
输入一个字符串 S,由小写字母构成,长度不超过 $10^6$。
aaxoaaaaa
输出格式
答案输出占一行,输出一个整数,表示子串 E 的长度。
2
因为求的是最长的 E
,而按照题意,E
不能重叠,所以 E
最长就是 length / 3
(此时 A
和 B
都是空串),因此从大到小枚举所有可能的长度 len
就可以了。
for (int len = length / 3; len >= 1; len--) {
t
从 len + 1
开始枚举,最多到 length - 2 * len
,因为后面的 EBE
最少需要占用 len + len
个长度,此时 B
是空串。
for (int t = len + 1; t <= length - 2 * len; t++) {
对于每一个枚举的 t
,next[t]
表示从该字符 s[t]
开始,有长度为多少的字符串,是与整个字符串开头的那么多个字符串相等的,显然,为了满足题目要求,next[t]
必须大于 len
。
if (next[t] < len) { continue; // 长度不满足要求,继续 }
现在,我们枚举了开头长度为 len
的 E
,并且在中间那段找到了一个 t
开始的位置,可以保证有大于或者等于 len
个字符与字符串开头是匹配的,所以,我们只需要需要找到最后一个 E
。
由于题目要求最后一个 E
必须是字符号结尾,所以直接判断 next[length - len + 1]
是不是大于等于 len
就可以了。
if (next[length - len + 1] < len) { continue; }
如果满足,那么说明当前的 len
就是答案。在整个循环中保留最大的 len
即可。
ans = max(ans, len);
事实上,得到了一个答案,直接输出就可以停止了,不需要继续枚举更短的 len
。
另外注意到 if (next[length - len + 1] < len)
判断与 t
无关,所以提到循环外面,否则可能会超时。
#include <bits/stdc++.h> #define MAX_LEN 1000007 using namespace std; void print(const char *t, const int *next, int n) { for (int i = 1; i <= n; i++) { printf("%c%c", t[i], i == n ? '\n' : '\t'); } for (int i = 1; i <= n; i++) { printf("%d%c", next[i], i == n ? '\n' : '\t'); } } int *getNext(const char *t, int n) { int *next = (int *) malloc(sizeof(int) * (n + 1)); next[1] = n; int p = 1; while (p < n && t[p] == t[p + 1]) p++; next[2] = p - 1; int k = 2, l; for (int i = 3; i <= n; i++) { p = k + next[k] - 1; l = next[i - k + 1]; if (i + l <= p) next[i] = l; else { int j = p - i + 1; if (j < 0) j = 0; while (i + j <= n && t[i + j] == t[j + 1]) j++; next[i] = j; k = i; } } return next; } int main() { char s[MAX_LEN] = {0}; scanf("%s", s + 1); int length = strlen(s + 1); int *next = getNext(s, length); for (int len = length / 3; len >= 1; len--) { if (next[length - len + 1] < len) { continue; } for (int t = len + 1; t <= length - 2 * len; t++) { if (next[t] < len) { continue; // 长度不满足要求,继续 } printf("%d\n", len); return 0; } } return -1; }