判断是否是回文的算法时间复杂度(回文串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;
}