[数据结构与算法]【Leetcode】647. Palindromic Substrings

题目地址：

https://leetcode.com/problems/palindromic-substrings/

给定一个字符串$s$，求其所有的不同回文子串的个数。两个回文子串不同当且仅当其中心位置不同，或者中心位置相同但半径不同。

可以用Manachar算法。该算法可以线性时间内求出以$s[i]$为中心的最长回文子串的半径长度$l$，那么其为中心的回文子串个数就是$l$。对每个$s[i]$累加$l$即可。Manachar算法参考https://blog.csdn.net/qq_46105170/article/details/123368095。代码如下：

public class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder("$#");
        for (int i = 0; i < n; i++) {
            sb.append(s.charAt(i)).append('#');
        }
        char[] chs = sb.append('^').toString().toCharArray();
        int[] p = new int[chs.length];
        
        int res = 0, mr = 0, mid = 0;
        for (int i = 1; i < chs.length - 1; i++) {
            if (i < mr) {
                p[i] = Math.min(p[2 * mid - i], mr - i);
            } else {
                p[i] = 1;
            }
            
            while (chs[i - p[i]] == chs[i + p[i]]) {
                p[i]++;
            }
            
            if (i + p[i] > mr) {
                mr = i + p[i];
                mid = i;
            }
            
            res += p[i] >> 1;
        }
        
        return res;
    }
}

时空复杂度$O(n)$。