Visits: 74

计蒜客 – 匹配格式

有一字符串 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;
}