忘れてはいけないManacherアルゴリズムノート

Manacherアルゴリズム
概要
Manacherアルゴリズムは主に最長回文サブ列を判断する問題に応用される.
Manacherアルゴリズムの手順
手順を言う前に、暴力的な解決策についてお話しします.文字列の各文字を遍歴し、各文字を中心に、外に拡大し、外に拡大する最大長さ、すなわち最長回文サブ列の長さを記録します.コードの最後の表示
本題に戻りますが、Manacherアルゴリズムはどのように解決されたのかを話します.
4つのケースに分けられ、4つのケースを話す前に、アルゴリズムのいくつかの基礎変数:C,R,i,i’,pArr[i]を明確にし、これらが何をしているのかを説明します.

C:Rに対応する中心文字を表す

R:回文子列の右境界を表す:これは少し違和感があるかもしれませんが、このRは増加するしかありません.それは、右へ遍歴する過程で、最後の回文子列の右境界

を記録しています.

i:遍歴中に対応する文字インデックス

i’:およびi C対称文字インデックス

pArr[i]:iを中心とする回文半径(長さをiそのものとする)

を表す.
これらの変数の意味を説明し、次の手順に従います.

iがRの外にいるとき、暴力的に拡大するしかなく、最適化されず、拡張に成功し、Rは

増加した.

iがR内にあるとき,iがC対称のi’について,

i+i’の回文半径の後に範囲がRを超える場合、拡張することなく、直接答え

を出す.

i+i’の回文半径の後に範囲がRに及ぶ場合、拡張することなく、直接答え

を出す.

i+i′の回文半径の後の範囲がR内である場合、外へ拡大、拡大に成功し、Rは

増加する.

実装コードを見てみましょう.(ああ、これはいつ忘れられるか分かりません.私は絶望しています.)

/**
 * Author:markusZhang
 * Date:Create in 2020/7/27 21:55
 * todo: Manacher  ：           
 */
public class Manacher_Str {
    /**
     *     
     */
    public static int process_1(String s){
        if (s == null || s.length() == 0){
            return 0;
        }
        char []str = s.toCharArray();
        str = manageStr(str);
        int max = Integer.MIN_VALUE;
        for (int i=0;i<str.length;i++){
            int len = 1;
            int left = i-1;
            int right = i+1;
            while(left > -1 && right < str.length){
                if (str[left] == str[right]){
                    len++;
                }else{
                    break;
                }
                left--;
                right++;
            }
            max = Math.max(max,len);
        }
        return max-1;
    }
    /**
     *         
     */
    public static int process_2(String s){
        if (s == null || s.length() == 0){
            return 0;
        }
        char []str = s.toCharArray();
        str = manageStr(str);
        //                 
        int max = Integer.MIN_VALUE;//       
        int []pArr = new int[str.length];//                    
        int C = -1;//     
        int R = -1;//           
        for (int i = 0 ; i < str.length ; i++){
            //       ，i R  ？        1，   R   ，   i R    i'         
            pArr[i] = i<R?Math.min(pArr[2*C-i],R-i):1;
            while(i-pArr[i] > -1 && i+pArr[i] < str.length){
                if (str[i-pArr[i]] == str[i+pArr[i]]){
                    pArr[i]++;
                }else{
                    break;
                }
            }
            if (i+pArr[i] > R){
                R = i+pArr[i];
                C = i;
            }
            max = Math.max(max,pArr[i]);
        }
        return max-1;
    }
    /**
     *                      '#'
     */
    private static char[] manageStr(char[] str){
        StringBuilder sb = new StringBuilder();
        sb.append("#");
        for (int i=0;i<str.length;i++){
            sb.append(str[i]);
            sb.append("#");
        }
        return sb.toString().toCharArray();
    }
    public static void main(String[] args) {
        String s = "babad";
        System.out.println(process_1(s));

        System.out.println(process_2(s));
    }
}