Leetcode 回文子串

Day 16

学习中心扩展法

class Solution {
    public int countSubstrings(String s) {
        // 从中心扩展，
        int count = 0;
        int n = s.length(); 
        // 字符串长度分奇数和偶数，但回文中心的可能性是确定的
      
        // 枚举所有的回文中心
        for(int i = 0;i<2*n-1;i++){
            // 偶数是中心两个字符，奇数是中心一个字符，但注意这里的i是所有可能回文中心的编号索引
            int l = i/2, r = i/2 + i%2;
            while(l>=0&&r<n){
                if(s.charAt(l--) == s.charAt(r++)){
                    count++;
                }else{
                    break;
                }
            }

        }
        return count;
    }
}

Manacher 算法

class Solution {
    public int countSubstrings(String s) {
        // 从中心扩展，
        int num = s.length();
        StringBuffer t = new StringBuffer("$#");
        for(int i =0;i<num;i++){
            t.append(s.charAt(i));
            t.append('#');
        }
        int n = t.length();
        t.append('!');
        // System.out.println(t);

        int[] f = new int[n];
        int center = 0, right_radius = 0,ans = 0;

        for(int i = 1;i<n;i++){

            // 在现存的回文子串半径内
            if(i<right_radius){
                // 对称点的回文半径是否小于最大半径，若大于，则为到边界的距离，否则为对称点回文半径
                f[i] = Math.min(f[2*center-i],right_radius-i+1);
            }else{
                f[i] = 1;
            }

            // 向外扩展

            while(t.charAt(i+f[i])==t.charAt(i-f[i])){
                // 如果可以往外拓展则增大半径
               f[i]++; 
            }

            if(i+f[i]-1 > right_radius){
                center = i;
                right_radius = center+f[i]-1;
            }
            // 子串数目与回文中心半径的关系：回文半径为r，自己加了#在字符之间
            ans +=f[i]/2;
        }

        return ans;
    }
}

开头和结尾的两个字符一定不相等，循环就可以在这里终止。