判断是否是回文的算法时间复杂度（回文串manacher算法的理解）

判断是否是回文的算法时间复杂度（回文串manacher算法的理解）在Ri情况下，回文串的中心点的位置Ci描述Ri从左到右在计算回文串时，记录的回文串里，末尾最后右边的位置

Manacher算法特点

•对字符串间隔和头尾都插入#，使得回文串都有中心

•以中心扩散算法为基础，根据回文串对称特性，减少计算

变量	描述
Ri	从左到右在计算回文串时，记录的回文串里，末尾最后右边的位置
Ci	在Ri情况下，回文串的中心点的位置
Li	在Ri情况下，回文串的最左边的位置
i	当前准备计算回文串的中心位置
j	当前位置i以Ci为中心的对称位置，j = Ci-(i-Ci) = 2Ci-i
RL[x]	以x为中心位置的回文串的半径

分支条件		RL[i]的计算
i < Ri	RL[j] < Ri - i	等于RL[j]
	RL[j] >= Ri - i	在Ri-i为半径的基础上扩散计算
i >= Ri		扩散计算

部分代码：

public int calcLongestPalindrome(String s) { //字符之间和头尾都插入#（s中不存在的字符） int p = s.length(); StringBuilder sb = new StringBuilder(s); while (p >= 0) { sb.insert(p '#'); p--; } int nlen = sb.length(); int max = 0; int[] RL = new int[nlen]; int Ri = 0 Ci = 0 j = 0; int left right; //循环从左到右计算RL，同时记录max，Ri，Ci for (int i = 0; i < nlen; i ) { j = 2 * Ci - i; //按图中分支条件计算RL[i] if (i < Ri) { RL[i] = RL[j] < Ri - i ? RL[j] : Ri - i; } else { RL[i] = 1; } //这里三种分支合并处理了 //分别是：RL[i]=RL[j] // 以Ri-i为半径扩散 // 直接以i为位置中心扩散计算 left = i - RL[i]; right = i RL[i]; while (left >= 0 && right < nlen && (sb.charAt(left) == sb.charAt(right))) { RL[i] ; left--; right ; } if (right - 1 > Ri) { //更新Ri Ci Ri = right - 1; Ci = i; } if (RL[i] > max) { // 更新max max = RL[i]; } } return max - 1; }