アルゴリズム学習——文字列の中で最も長い回文のサブ列を探す

文章は公衆番号「インターネット捜査」から転載された.

/**
 * @author xiaoshi on 2018/9/24.
 * Happy Mid-Autumn Festival
 */
public class PlalindromeString {

    //            ，       
    @Deprecated
    private boolean isPlalindrome(String s) {
        int len = s.length();
        for(int i = 0; i < len / 2; i++) {
            if(s.charAt(i) != s.charAt(len - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    //       ，         #
    private String preHandleString(String s) {
        StringBuffer sb = new StringBuffer();
        int len = s.length();
        sb.append('#');
        for(int i = 0; i < len; i++) {
            sb.append(s.charAt(i));
            sb.append('#');
        }
        return sb.toString();
    }

    //         
    public String findLongestPlalindromeString(String s) {
        //        
        String str = preHandleString(s);
        //         
        int len = str.length();
        //    
        int rightSide = 0;
        //            
        int rightSideCenter = 0;
        //                  （    ）
        int[] halfLenArr = new int[len];
        //       
        int center = 0;
        //         
        int longestHalf = 0;
        for(int i = 0; i < len; i++) {
            //         
            boolean needCalc = true;
            //            
            if(rightSide > i) {
                //     rightSideCenter     
                int leftCenter = 2 * rightSideCenter - i;
                //            
                halfLenArr[i] = halfLenArr[leftCenter];
                //         ，    
                if(i + halfLenArr[i] > rightSide) {
                    halfLenArr[i] = rightSide - i;
                }
                //                       ，       
                if(i + halfLenArr[leftCenter] < rightSide) {
                    //       
                    needCalc = false;
                }
            }
            //     
            if(needCalc) {
                while(i - 1 - halfLenArr[i] >= 0 && i + 1 + halfLenArr[i] < len) {
                    if(str.charAt(i + 1 + halfLenArr[i]) == str.charAt(i - 1 - halfLenArr[i])) {
                        halfLenArr[i]++;
                    } else {
                        break;
                    }
                }
                //         
                rightSide = i + halfLenArr[i];
                rightSideCenter = i;
                //        
                if(halfLenArr[i] > longestHalf) {
                    center = i;
                    longestHalf = halfLenArr[i];
                }
            }
        }
        //        #
        StringBuffer sb = new StringBuffer();
        for(int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) {
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }

}

/**
 * @author lixin on 2018/9/24.
 */
public class Main {

    public static void main(String[] args) {

        PlalindromeString ps = new PlalindromeString();

        String[] testStrArr = new String[] {
            "abcdcef",
            "adaelele",
            "cabadabae",
            "aaaabcdefgfedcbaa",
            "aaba",
            "aaaaaaaaa"
        };

        for(String str : testStrArr) {
            System.out.println(String.format("    : %s", str));
            System.out.println(String.format("      : %s", ps.findLongestPlalindromeString(str)));
            System.out.println();
        }

    }

}

実行結果:原字列:abcdcef最長回文列:cdc原字列:adaelle最長回文列:elele原字列:cabadabae最長回文列:abadaba原字列:aaabcdefgfedcbaa最長回文列:aaabcdefgfedcbaa原字列:aabaa最長回文列:aaaaaaaaaaa