P11276 第一首歌 题解

Sky_Maths · 2024-11-20 07:55:44 · 题解

约定

对于字符串 a, b，令 a + b 代表将 a 与 b 拼接而成的字符串。

思路

首先 t = s + s 是一个上界。

若 |t| = 2|s| - len < 2|s|，则必有 s_{1\dots len} 是 s 的一个 border。

证明可以考虑 t_{1\dots |s|} = t_{|t| - |s| + 1\dots |t|} = s，考察两个 s 的重叠部分即可，且重叠部分的交的长为 len，容易发现这是充要条件。

那么我们要求 |t| 尽可能小，只要使 len 尽可能大即可，求最大的 len 即求 s 的最长 border，可以用 kmp 实现。

代码

const int N = 1e6 + 9;
int n;
int fail[N];
char s[N];

void skymaths() {
    scanf(" %s", s + 1); n = strlen(s + 1);
    int p = 0;
    fail[0] = -1;
    rep (i, 2, n) {
        while (p != -1 && s[p + 1] != s[i]) p = fail[p];
        fail[i] = ++p;
    }
    printf("%s%s\n", s + 1, s + p + 1);
}