최 장 회 문 꼬치 (말 라 차 알고리즘)

1568 단어 알고리즘
    /*      (Manacher        -_-)
                               。       
                     ,              ,                      (            ,           )
    */
    public String longestPalindrome(String s) {
        //    s,     '#',abc  #a#b#c#
        StringBuffer sb = new StringBuffer();
        sb.append('#');
        for(int i=0; ii){
                int leftCenter = rightBoundCenter * 2 - i; //          i    
                halfArr[i] = halfArr[leftCenter];

                //        
                if(i+halfArr[i] > rightBound){
                    halfArr[i] = rightBound - i;
                }

                //    ,     
                if(i + halfArr[leftCenter]=0 && rightlongestPal){
                    center = i;
                    longestPal = halfArr[i];
                }

            }
        }

        StringBuffer rsb = new StringBuffer();
        //     '#',   #    
        for(int i=center-longestPal+1; i<=center+longestPal; i += 2){
            rsb.append(str.charAt(i));
        }
        String palindrome = rsb.toString();
        return palindrome;
    }

좋은 웹페이지 즐겨찾기