想到使用 manacher
先放代码，板子来自蒋老师，https://www.cnblogs.com/WIDA/p/17633758.html#马拉车manacher
std::vector<int> manacher(std::string s) {std::string t = "#";for (auto c : s) {t += c;t += '#';}int n = t.size();std::vector<int> r(n);for (int i = 0, j = 0; i < n; i++) {if (2 * j - i >= 0 && j + r[j] > i) {r[i] = std::min(r[2 * j - i], j + r[j] - i);}while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {r[i] += 1;}if (i + r[i] > j + r[j]) {j = i;}}return r;
}
首先核心要求的就是 r[i] ，表示在变换后的串 t 中，以 i 为中心，最长能扩展出的回文半径
板子的开头是对字符串进行处理
主循环中，i 是当前要求的中心，j 是“当前最优中心”，即 它对应的回文向右延伸得最远
while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {r[i] += 1;}
这部分是好理解的，就是逐个判断当前中心能不能继续往外延展了
关键是
if (2 * j - i >= 0 && j + r[j] > i) {r[i] = std::min(r[2 * j - i], j + r[j] - i);
}
这也是保证复杂度的核心部分
2 * j - i 是指 i 关于 j 的镜像点，之所以要这个点是因为如果 i 落在以 j 为中心的那个大回文内部，那么根据回文对称性：i 附近的一部分回文信息，可以直接从 mirror 那里得到，进而可以少计算一些信息
而 j + r[j] 就是 j 对应的大回文右边界，因为当前点 i 落在以 j 为中心的那个“已知最右回文”内部才能像上面说的那样借用已有的信息
更新时就是对应点的半径信息和右边界到 i 距离的较小者
这样赋了初值后再暴力更新
最后再判断最优边界在这轮后有没有被刷新
对于这道题，使用板子的时候，就是要从 r[i] 出发求原串最长回文子串长度
在这种插 # 的写法下：原串中的最长回文长度 = max(r[i] - 1)
因为：
- 在变换串中半径包含了分隔符
- 去掉这些影响后，原串长度正好是
r[i] - 1
例如：
"aba"的中心半径r = 4（变换后是"#a#b#a#"）- 原串回文长度就是
4 - 1 = 3（注意是从半径到长度） "abba"变换后对应中心也会有r = 5- 原串长度就是
5 - 1 = 4
int ans = 0;
for (int i = 0; i < r.size(); i++) {ans = std::max(ans, r[i] - 1);
}
于是完整代码就是
std::vector<int> manacher(std::string s) {std::string t = "#";for (auto c : s) {t += c;t += '#';}int n = t.size();std::vector<int> r(n);for (int i = 0, j = 0; i < n; i++) {if (2 * j - i >= 0 && j + r[j] > i) {r[i] = std::min(r[2 * j - i], j + r[j] - i);}while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {r[i] += 1;}if (i + r[i] > j + r[j]) {j = i;}}return r;
}class Solution {
public:int countSubstrings(string s) {auto r = manacher(s);int ans = 0;for (int i = 0; i < r.size(); i++) {ans += max(0, (r[i] - 1 + 1) / 2);}return ans;}
};