Manacher

解决问题

求最长回文子串的长度

Manacher.pdf

AcWing 3188. manacher算法

给定一个长度为 nn 的由小写字母构成的字符串，求它的最长回文子串的长度是多少。
输入格式
一个由小写字母构成的字符串。
输出格式
输出一个整数，表示最长回文子串的长度。
数据范围
1≤n≤107
输入样例：
abcbabcbabcba
输出样例：
13

import java.util.*;
public class Main {
    static final int N = 20000010;
    static char[] a, b = new char[N];
    static int[] p = new int[N];
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a = sc.next().toCharArray();
        n = init();
        manacher();
        int res = 0;
        for (int i = 0; i < n; i++)
            res = Math.max(res, p[i]);
        System.out.println(res - 1);
    }
    static void manacher() {
        int mid = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i < r) p[i] = Math.min(p[mid * 2 - i], r - i);
            else p[i] = 1;
            while (b[i + p[i]] == b[i - p[i]]) {
                p[i]++;
            }
            if (r < p[i] + i) {
                r = p[i] + i;
                mid = i;
            }
        }
    }
    static int init() {
        int k = 0;
        b[k++] = '$';
        b[k++] = '#';
        for (char c : a) {
            b[k++] = c;
            b[k++] = '#';
        }
        b[k++] = '^';
        return k;
    }
}