package code;

public class Code214 {

	/*
	 * 求最长的回文
	 */
	public int[] calPalindrome(String s){
		StringBuilder sb=new StringBuilder();
		int i,j;
		for(i=0;i<s.length();i++){
			sb.append("#"+s.charAt(i));
		}
		sb.append("#");
		int n=s.length();
		
		int[] p=new int[2*n+1];
		int mx=0;
		int index=0;
		int idx=0;
		for(i=1;i<=2*n;i++){
			if(mx>i)
				p[i]=p[2*index-i]>mx-i?mx-i:p[2*index-i];
			else 
				p[i]=1;
			for(;i-p[i]>=0 && i+p[i]<=2*n && sb.charAt(i-p[i])==sb.charAt(i+p[i]);p[i]++)
				;
			if(i+p[i]>mx){
				mx=i+p[i];
				index=i;
			}
		}
		return p;
	}
	public int min(int a,int b){
		return a>b?b:a;
	}
 public String shortestPalindrome(String s) {
 	int n=s.length();
 	if(n==0)
 		return "";
 	int[] p=calPalindrome(s);
 	int maxLen=0;
 	int i,k=0;
 	for(i=1;i<2*n;i++){
 		if(p[i]==i+1)
 			k=i;
 	}
 	StringBuilder ans=new StringBuilder();
 	int j;
 	k=p[k]-2;
 	for(j=n-1;j>k;j--){
 		ans.append(s.charAt(j));
 	}
 	ans.append(s);
 return ans.toString();
 }
 public static void main(String[] args){
 	String s="abc";
 	System.out.println(new Code214().shortestPalindrome(s));
 }
}