【LeetCode】5.Longest Palindromic Substring-Java実装

1. テーマ説明:

2. 構想分析:

3. Javaコード:

1.タイトルの説明:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: “babad” Output: “bab” Note: “aba” is also a valid answer.
Example:
Input: “cbbd” Output: “bb”
2.構想分析:
タイトルは最大回文文字列を探すことであり、以下の2つの考え方があり、その中の第2の考え方は経典のManacherアルゴリズムである:(1)考え方1:各要素を最初から最後まで遍歴し、それぞれ各要素を中心としてこの要素を中心とした回文文字列を両側に広げて探す.時間複雑度はO(n^2).
(2)考え方2:古典的なManacherアルゴリズムは,時間責任度をO(n)に低減できる.まず、Manacherアルゴリズムは、奇数の長さの文字列と偶数の長さの文字列を一緒に考慮する巧みな方法を提供し、具体的には、元の文字列の隣接する2つの文字の間に1つの区切り文字を挿入すると同時に、最初の最後にも1つの区切り文字を追加し、区切り文字の要求は元の文字列に現れず、一般的には#番号を使用することができる.次に例を示します.
Len配列の性質:
Manacherアルゴリズムは、1つの補助配列Len[i]で文字T[i]を中心とした最長文字列の最右文字からT[i]までの長さ(回文文字列の半径)を表し、例えばT[i]を中心とした最長文字列がT[l,r]である場合、Len[i]=r-i+1となる.
上記の例では、Len[i]配列は次のようになる.
Len配列には、元の文字列SにおけるLen[i]-1の長さであるという性質があり、証明については、まず変換された文字列Tにおいて、すべての文字列の長さが奇数であるとすると、T[i]を中心とした最長文字列については、その長さは2*Len[i]-1となり、観察により、Tにおけるすべての文字列の長さは、ここで、区切り文字の数は他の文字の数より1多いに違いない.すなわち、Len[i]個の区切り文字があり、残りのLen[i]-1個の文字は元の文字列から来ているので、この文字列の元の文字列の長さはLen[i]-1である.
この性質があれば,原問題はすべてのLen[i]を求めることに転化する.線形時間の複雑さの中ですべてのLenを求める方法を紹介する.
Len配列の計算:
まず左から順にLen[i]を計算し、Len[i]を計算するとLen[j](0<=j)
3.Javaコード: :GiHubのホームページを参照
コード1:時間複雑度O(n^2)

/**
 *   1：      
 */
public String longestPalindrome(String s) {
    int left = 0;
    int right = 0;
    for (int i = 0; i < s.length(); i++) {
        //  s[i]   
        int len1 = expandAroundCenter(s, i, i);
        //  s[i] s[i+1]   
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > right - left + 1) {
            left = i - (len - 1) / 2;
            right = i + len / 2;
        }
    }
    return s.substring(left, right + 1);
}

private int expandAroundCenter(String s, int center1, int center2) {
    int left = center1;
    int right = center2;
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

コード2:時間複雑度O(n)

/**
 * Manacher   ，       
 */
public String manacher(String s) {
    //               
    char[] charArray = s.toCharArray();
    StringBuilder sb = new StringBuilder("#");
    for (int i = 0; i < charArray.length; i++) {
        sb.append(charArray[i]);
        sb.append("#");
    }

    int maxCenter = 0;
    int maxRight = 0;
    int oriLen = 0;
    int oriRight = 0;

    int[] len = new int[sb.length()];
    for (int i = 0; i < len.length; i++) {
        // j    maxCenter      
        int j = 2 * maxCenter - i;
        len[i] = maxRight > i ? Math.min(len[j], maxRight - i) : 1;

        while (i + len[i] < sb.length() && i - len[i] >=0 && sb.charAt(i + len[i]) == sb.charAt(i - len[i])) {
            len[i]++;
        }

        //                       
        if (maxRight - maxCenter + 1 < len[i]) {
            maxRight = i + len[i] - 1;
            maxCenter = i;
            oriLen = len[i] - 1;
            oriRight = (maxRight - 1) / 2;
        }
    }

    return s.substring(oriRight - oriLen + 1, oriRight + 1);
}