回文子串与Manacher算法

问题描述以及一般思路

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

一个满足回文结构的字符串一定是“中心对称”的。那么我们可以用$f(i)$来表示以i为中心的回文字符串最大半径。这里的半径是指左右端点到中心的距离。回文字符串的长度可以是偶数个，那么中心就不好描述。这里我们可以在每个字符串两边插入一个字符#，来使所以的回文字符串都是奇数长度。

以一个字符作为中心的回文字符串的长度可以由其构成的最大回文字符串长度确定。那么我们可以以每一个字符串为中心（包括插入的新字符），遍历一遍即可计算出输入的字符串中有多少个回文字符串。

相关代码如下：

/**
 * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串.
 */
public class CountSubString {
    public int countSubstrings(String s) {
        int res = 0;
        var cc = s.toCharArray();
        var ss = new char[cc.length*2+1];
        ss[0] = '#';
        int t = 1;
        for (int i = 0; i < cc.length; i++) {
            ss[t]=cc[i]; 
            t++;
            ss[t]='#';
            t++;
        }
        for (int i = 0; i < ss.length; i++) {
            res += helper(ss, i);
        }
        return res;
    }


    private int helper(char[] ss, int i){
        int c = 1;
        for (int j = 1; j+i < ss.length&&i-j>=0; j++) {
            if(ss[i-j]!=ss[i+j]){
                break;
            }
            c++;
        }
        return c/2;
    }
}

一般思路的局限性

可以得知，我们用这种遍历的方法，可以有$O(n^2)$的时间复杂度，空间复杂度为$O(1)$。我们发现，每次计算以i字符为中心的回文字符串最大半径的时候，可以保存一些状态来减小时间复杂度。这里就是Manacher算法的关键点。

Manacher算法

Manacher算法与我们之前的思路相同，也是计算中心字符构成回文字符串的最大半径。但是该算法的优越之处在于使用了之前计算的f，来节省时间。

假设我们已经计算了0到i-1个字符的f，那么我们可以得知在0-（i-1）区间内的回文字符串的最大右端点。即最大的$f(k)+k-1$。我们把它表示为rightMax，同时其对应的中心字符下标为iMax。

这时，我们遍历字符串时，会有两种情况：

1. 如果$i<=iMax$，我们将i关于iMax的对称点设为j，及$i+j=2*iMax$，那么，我们通过对称性可知，f(j)应该是和f（i）差不多的。所以$f(i) = min{ f(j), rightMax-iMax+1 }$，这里为什么要用i-iMax+1来约束$f(i)$呢？因为我们想让它的中间结果落在rightMax范围内（因为超出的部分还没有更新）。
2. 如果$i>iMax$，$f(i)$先设为1
3. 第三步，更新步骤，这里需要比较下标分别为$i-f(i)+1$与$i+f(i)-1$的字符串值，如果相等，则$f(i)++$。思想和一般算法计算回文字符串长度的一致。
4. 更新步骤第二布，更新rightMax和iMax，如果我们此时计算的$i+f(i)-1>rightMax$，那么我们更新一次rightMax和iMax;

TIPS:

• 第三步比较字符时，我们可以在整个字符串的开始和结尾处加上两个其他字符，使其自动退出。
• 最后的结果为每个f(i)/2之和.

相关代码

public int countSubstrings(String s) {
        char[] tt = new char[s.length()*2+3];
        int k = 2;
        int len = tt.length-1;
        tt[0] = '!';tt[1] = '#';
        for (char c :
                s.toCharArray()) {
            tt[k++] = c;
            tt[k++]  = '#';
        }
        tt[k] = '?';

        int rightMax = 0, iMax = 0;
        int[] f = new int[tt.length];
        int res = 0;
        for (int i = 2; i < len; i++) {
            if (i<=rightMax){
                f[i] = Math.min(f[2*iMax-i], rightMax-i+1);
            }else{
                f[i] = 1;
            }
            while (tt[i+f[i]]==tt[i-f[i]]){
                f[i]++;
            }
            if(i+f[i]-1>iMax){
                iMax = i+f[i]-1;
                rightMax = i;
            }
            res += f[i]/2;
        }
        return res;
    }