085 Manacher算法 求str中最长回文子串的长度
Table of Contents

ac

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    /**
     * https://blog.csdn.net/qq_26437925/article/details/52181738
     */
    public static void main(String[] args) throws Exception {
        String s = reader.readLine();
        char[] ch = s.toCharArray();
        char[] arr = new char[2 * ch.length + 1];
        int len = arr.length;
        int chi = 0;
        for(int i = 0; i < len; i++){
            arr[i] = (1&i) == 0 ?'#' : ch[chi++];
        }
        //  p[i] 表示 以i位置为中心的回文半径长(其长度减去1,表示在原字符串中以i为中心的回文长度)
        // 包括自己,往外扩的时候,能够成回文的半径长
        int[] p = new int[len];
        // 表示 回文半径最长的位置的下一个位置(pR总是比上一个pR值要大的)
        int pR;
        // 表示 回文中心点,pR更新时index要跟着更新,否则index不用更新
        int index;

        // index = 0 的情况
        p[0] = 1;
        index = 0;
        pR = 1;
        // index = 1 的情况
        p[1] = 2;
        index = 1;
        pR = 3;

        int maxlen = 1;
        for(int i = 2;i<len;i++){
            int _i = index - (i - index);   //i的对称位置i'
            int index_left = index - p[index] + 1;  // index的左大
            int index_right = pR - 1;    // index的右大
            int _i_left = _i - p[_i] + 1;    // i的对称位置i'的左大

            if (_i < index_left) {
                int j = i + 1;
                int _j = i - 1;
                while (_j >= 0 && j < len && arr[_j] == arr[j])
                {
                    _j--;
                    j++;
                    if (_j < 0 || j >= len) {
                        break;
                    }
                }
                p[i] = j - i;
                pR = j; // 更新pR 和 index
                index = i;
            }else{
                if(_i_left < index_left){
                    p[i] = index_right - i + 1;
                }else if(index_left < _i_left){
                    p[i] = p[_i];
                }else {
                    // 往外扩
                    int j = pR;
                    int _j = i - (pR - i);
                    while ( _j >= 0 &&  j < len && arr[_j] == arr[j])
                    {
                        _j--;
                        j++;
                        if (_j < 0 || j >= len) {
                            break;
                        }
                    }
                    p[i] = j - i;
                    pR = j; // 更新pR 和 index
                    index = i;
                }
            }
            if (p[i] - 1 > maxlen) {
                maxlen = p[i] - 1;
            }
        }
        System.out.println(maxlen);
    }


}
/*
abc1234321ab
#a#b#c#1#2#3#4#3#2#1#a#b#
 */

_i < index_left

            index
                  p[index]        pR
    index_left    index_right
_i                                    i

只能从i左右不断的判断相等求

_i < index_left (利用对称性)

_i_left < index_left

                     index
                                    p[index]  pR
    index_left                      index_right
              _i               i
_i_left

  a                   c                          b

a != b  a == c 所以 b != c
那么 p[i] 最大也就是到b,也即 index_right - i + 1

_i_left > index_left

                      index
                                      p[index]      pR
index_left                            index_right
                _i               i
   _i_left

  a                     c                     b

a != c  a == b 所以 b != c

ci距离,即 a_i距离,则有
p[i] = p[_i]

_i_left == index_left

可以知道至少是i到pR-1,进一步往外扩去求解