LeetCode647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例1
代码语言：javascript复制输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"示例2
代码语言：javascript复制输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"Manacher 算法
代码语言：javascript复制/**
* Manacher
*/
public int countSubstrings(String s) {
int len = s.length();
StringBuilder sb = new StringBuilder("$#");
// 解决回文串奇数长度和偶数长度的问题，处理方式是在所有的相邻字符中间插入 '#' ，这样可以保证所有找到的回文串都是奇数长度的
for (int i = 0; i < len; i) {
sb.append(s.charAt(i)).append('#');
}
// 设置哨兵，到了边界就一定会不相等，从而结束循环
sb.append('%');
len = sb.length();
// 用 radius[i] 来表示以 sb 的第 i 位为回文中心，可以拓展出的最大回文半径
int[] radius = new int[len];
// 维护 当前最靠右的回文右端点 maxRight , 以及这个回文右端点对应的回文中心 maxMid
int maxMid = 0;
int maxRight = 0;
int rs = 0;
// 剪枝
for (int currMid = 2; currMid < len - 2; currMid ) {
// radius[currMid] = [maxRight - currMid, radius[currMid 关于 maxMid 对称点]]
// currMid 在当前最大回文子串内：
// 回文串的性质，关于回文中心对称的两边一样，因此当前点的回文半径至少是对称点的回文半径
// 因此 currMid 处的 回文半径 最小为 对称点的最大回文半径
// 特殊情况：currMid 对称点的最大回文半径 > maxRight
// 此时无法取到整个对称点的最大回文半径 , 但最小可以是 currMid 到 maxRight 之间
// currMid 不在当前最靠右的回文串内：
// 以 currMid 为中心 1 为回文半径
radius[currMid] = currMid <= maxRight ? Math.min(maxRight - currMid 1, radius[2 * maxMid - currMid]) : 1;
// 中心拓展
while (sb.charAt(currMid radius[currMid]) == sb.charAt(currMid - radius[currMid])) {
radius[currMid] ;
}
// 动态维护 maxMid 和 maxRight
// 当前回文右端点 = 当前中心 最大回文半径 - 1 > 最大回文右端点
if (currMid radius[currMid] - 1 > maxRight) {
maxMid = currMid;
maxRight = currMid radius[currMid] - 1;
}
// 最长回文子串的结尾一定是 '#' , 因为如果结尾是有实际意义的字符，其两端一定都是 '#'
// 中心位置如果是 '#' 则半径为偶数
// # a # b [#] b # a # 此时回文半径为 4 , 4 >> 1 == 2
// 如果为实际意义的字符则半径为奇数向下取整
// # a # b # [currMid] # b # a # 此时回文半径为 5 , 5 >> 1 == 2
rs = radius[currMid] >> 1;
}
return rs;
}中心扩散
代码语言：javascript复制/**
* 中心扩散
*/
public int countSubstrings2(String s) {
int rs = 0;
int len = s.length();
// 对于一个长度为n的字符串，可以用它的任意一个字符当做中心点，所以中心点的个数是n。
// 还可以用它任意挨着的两个字符当做中心点，所以中心点是n-1，总的中心点就是2*n-1。
for (int mid = 0; mid < (len << 1) - 1; mid ) {
int left = mid >> 1;
int right = left (mid & 1);
while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
rs ;
left--;
right ;
}
}
return rs;
}
public int countSubstrings3(String s) {
int rs = 0;
int len = s.length();
for (int mid = 0; mid < len; mid ) {
int left = mid;
int right = mid;
while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
rs ;
left--;
right ;
}
}
for (int mid = 0; mid < len; mid ) {
int left = mid;
int right = mid 1;
while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
rs ;
left--;
right ;
}
}
return rs;
}
