【算法】最長回文子串-Manacher算法(hihoCoder 1032)

描述

小Hi和小Ho是一對好朋友，出生在資訊化社會的他們對程式設計産生了莫大的興趣，他們約定好互相幫助，在程式設計的學習道路上一同前進。

這一天，他們遇到了一連串的字元串，于是小Hi就向小Ho提出了那個經典的問題：“小Ho，你能不能分别在這些字元串中找到它們每一個的最長回文子串呢？”

小Ho奇怪的問道：“什麼叫做最長回文子串呢？”

小Hi回答道：“一個字元串中連續的一段就是這個字元串的子串，而回文串指的是12421這種從前往後讀和從後往前讀一模一樣的字元串，是以最長回文子串的意思就是這個字元串中最長的身為回文串的子串啦~”

小Ho道：“原來如此！那麼我該怎麼得到這些字元串呢？我又應該怎麼告訴你我所計算出的最長回文子串呢？

樣例輸入

3

abababa

aaaabaa

acacdas

樣例輸出

7

5

3

限制

時間限制:1000ms

單點時限:1000ms

記憶體限制:64MB

思路

參考http://blog.csdn.net/ggggiqnypgjg/article/details/6645824/

代碼

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n>||n<=)
           return;

        sc.nextLine();
        for(int i=;i<n;i++){
            String string = sc.nextLine();
            if(string.length()>)
                return;
            int l=*string.length()+;
            char s[]=new char[l];
            for(int j=;j<string.length();j++){
                    s[j*]='@';
                    s[j*+]=string.charAt(j);
            }
            s[l-]='@';
            int id=;
            int mx=;
            int p[] =new int[l];
            for(int j=;j<l;j++){
                if(mx>j){
                    p[j]=p[*id-j]>(mx-j)?(mx-j):p[*id-j];
                }else{
                    p[j]=;
                }
                while(p[j]+j<l&&j-p[j]>=&&s[p[j]+j]==s[j-p[j]]){
                    p[j]++;
                }
                if(p[j]+j>mx){

                    mx=p[j]+j;
                    id=j;

                }
            }
            int subs=;
            for(int j=;j<l;j++){
                if(subs<p[j])
                   subs=p[j];
            }
            System.out.println(subs-);

        }


    }

}