最長回文子列-マラ車アルゴリズム詳細解

マラ車アルゴリズムは主に最長回文子列問題を解くために用いられ、彼は問題を解く複雑さを線形に下げ、すごいアルゴリズムである.
次にleetcode第5題を例に、その原理と問題解決時の応用を紹介します.
文字列の中心点を計算すると、パリティが発生します.
回文列の中心点は2種類あり、長さが奇数であれば、回文列の中心は最も中間の文字、例えば「aba」の「b」である.長さが偶数の場合、「abba」の「bb」のような、文列の中心は最も中間の2文字の境界である.統一するために、マラ車アルゴリズムはまず文字列の各文字間(首尾両端を含む)に特殊な記号を挿入し、例えば#、この記号は元の文字列にない必要があります.
例えば文字列s=「babad」は、'#'を挿入して
      s="#b#a#b#a#d#"
そうすると、文字列の長さは奇数に違いありません.挿入された#番号の個数は必ず文字個数+1に等しいので、全長は偶数+奇数=奇数です.これにより,ループ時に元の文字列長のパリティを考慮する必要がなくなる.
配列pの計算方法:
一般的な方法は、中心点を中心に、文字列が返信文字列でなくなるまで半径を1つずつ拡張することです.しかし,このようにして全体のアルゴリズムの複雑さはO(n 2)O(n 2)である.マラ車アルゴリズムの鍵は,配列pを計算するためにエコー文字列の性質を巧みに適用することにある.
マラ車アルゴリズムは配列pを計算するプロセス全体で、2つの変数を更新しています.
id:回文サブストリングの中心位置mx:回文サブストリングの最後の位置
この2つの変数を使用すると、配列p全体を1回のスキャンで計算できます.重要な式は次のとおりです.
p[i] = min(mx-i, p[2 * id - i])
 
AC 8ms:

class Solution {
    public String longestPalindrome(String s) {
        if(s==null||s.length()<=1)
            return s;
        String t=transferString(s);
        int[] ans=manacherString(t);
        int index=ans[0];
        int ansR=ans[1];
        if(index>=0)
            return s.substring(index,index+ansR-1);
        return "";
    }
    public String transferString(String s){
        StringBuilder sb=new StringBuilder();
        sb.append("$");
        for(int i=0;ii?Math.min(mx-i,p[2*id-i]):1;
            while(s.charAt(i+p[i])==s.charAt(i-p[i]))
                p[i]++;
            if(mx