Manacher：线性时间最长回文子串

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

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 110000;            // 原始字符串最大长度

// Manacher 模板（不使用 std::string）
struct Manacher {
    // 变换后长度上限：2*MAXN + 少量哨兵
    static const int SZ = MAXN * 2 + 5;
    char t[SZ];    // 变换后的字符串：^ # a # b # ... # $
    int p[SZ];     // 半径数组（在 t 上的扩展长度）
    int m = 0;     // t 的实际长度（含终止符）

    // 构造变换串并计算 p[]
    // 输入：C 风格字符串 s（以 '\0' 结尾）
    void build(const char *s) {
        int n = (int)strlen(s);
        int k = 0;
        t[k++] = '&';   // 左哨兵，防止越界
        t[k++] = '#';
        for (int i = 0; i < n; ++i) {
            t[k++] = s[i];
            t[k++] = '#';
        }
        t[k++] = '^';   // 右哨兵
        t[k] = '\0';
        m = k;

        // 初始化半径数组
        memset(p,0,sizeof(p));

        // Manacher 主循环
        int center = 0, right = 0;
        for (int i = 1; i < m - 1; ++i) {
            int mirror = 2 * center - i;
            if (i < right) p[i] = min(right - i, p[mirror]);
            else p[i] = 1; // 长度至少是1

            // 暴力扩展：安全因为有哨兵
            while (t[i + p[i]] == t[i - p[i]]) ++p[i];

            // 更新中心与右边界
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
    }

    // 获取最长回文子串，返回长度；通过引用参数 l,r 返回原串上的左闭右闭索引（0-based）
    int longest(int &l, int &r) const {
        int best_len = 0, best_center = 0;
        for (int i = 1; i < m - 1; ++i) {
            if (p[i]-1 > best_len) {
                best_len = p[i]-1;
                best_center = i;
            }
        }
        if (best_len == 0) { l = 0; r = -1; return 0; }
        // 将 t 中的位置映射回原串的索引
        l = (best_center - best_len) / 2;
        r = l + best_len - 1;
        return best_len;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    static char s[MAXN + 5];
    if (scanf("%110000s", s) != 1) return 0;   // 读取一个单词（竞赛常用）
    // 若需读取整行（含空格），使用 fgets 或 fgets + 去除末尾换行

    Manacher man;
    man.build(s);

    int L, R;
    int len = man.longest(L, R);
    printf("%d\n", len);
    if (len > 0) {
        // 输出子串：注意 printf 的 %.*s 用法
        printf("%.*s\n", len, s + L);
    }
    return 0;
}

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

# Manacher：线性时间求最长回文子串。
# build(s) 后 longest() 返回 (长度, l, r)，[l, r] 是原串上的 0-based 闭区间；
# 无回文（空串）时返回 (0, 0, -1)。C++ 用 int& 出参，Python 改为元组返回。
# 变换串为 & # c1 # c2 # ... # ^，两端哨兵互不相等，扩展时无需判边界。
# C++ 用定长数组 MAXN=110000，Python list 按 len(s) 动态分配，没有长度上限。

IntSeq = list[int]  # p：半径数组，p[i] 为变换串上以 i 为中心的扩展长度
Text = list[str]  # t：变换后的字符序列，首尾各有一个哨兵


class Manacher:
    """t / p / m 与 C++ 成员一一对应；m 是含哨兵的变换串长度。"""

    t: Text
    p: IntSeq
    m: int

    def __init__(self) -> None:
        self.t = []
        self.p = []
        self.m = 0

    def build(self, s: str) -> None:
        """构造变换串并计算半径数组；可对同一对象反复 build 换新串。"""
        # 交错插入 '#' 后，任意回文长度都是奇数，一个数组即可同时处理奇偶回文。
        t: Text = ["&", "#"]
        for ch in s:
            t.append(ch)
            t.append("#")
        t.append("^")
        self.t = t
        self.m = len(t)
        self.p = [0] * self.m

        center = 0  # 当前已知最靠右回文的中心
        right = 0  # 该回文的右边界（不含）
        for i in range(1, self.m - 1):  # 跳过两个哨兵
            mirror = 2 * center - i  # i 关于 center 的对称点
            if i < right:
                # 对称点的半径受右边界限制，取两者较小值作为初值。
                self.p[i] = min(right - i, self.p[mirror])
            else:
                self.p[i] = 1  # 至少包含 i 自身
            # 暴力扩展；因为哨兵互不相等，最右/最左一定停得住。
            while self.t[i + self.p[i]] == self.t[i - self.p[i]]:
                self.p[i] += 1
            if i + self.p[i] > right:
                center = i
                right = i + self.p[i]

    def longest(self) -> tuple[int, int, int]:
        """返回 (最长回文长度, l, r)；无解返回 (0, 0, -1)。"""
        best_len = 0
        best_center = 0
        for i in range(1, self.m - 1):
            if self.p[i] - 1 > best_len:  # p[i]-1 正是该中心的原串回文长度
                best_len = self.p[i] - 1
                best_center = i
        if best_len == 0:
            return 0, 0, -1
        # 把变换串位置映射回原串下标：中心左侧有 (p[i]-1) 个原字符，间隔是 '#'。
        l = (best_center - best_len) // 2
        r = l + best_len - 1
        return best_len, l, r


if __name__ == "__main__":
    import sys
    data = sys.stdin.read().split()
    if data:
        s = data[0]
        solver = Manacher()
        solver.build(s)
        length, left, right = solver.longest()
        print(length)
        if length:
            print(s[left:right + 1])