左大
为关于某个点最大回文串的左位置右大
为关于某个点最大回文串的右位置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
(利用对称性)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
index p[index] pR index_left index_right _i i _i_left a c b a != c 而 a == b 所以 b != c c到i距离,即 a到_i距离,则有 p[i] = p[_i]
可以知道至少是i到pR-1,进一步往外扩去求解