leetcode@ [214]Shortest Palindrome

 1 class Solution {
 2 public: int* buildNext(string T){
 3         int i=1,j;
 4         int *next=new int[10000000];
 5         next[0]=0; next[1]=0;
 6         while(i<T.length()){
 7             j=next[i];
 8             while(j&&T[i]!=T[j]) j=next[j];
 9             next[i+1]=(T[i]==T[j])? j+1 : 0;
10             i++;
11         }
12         return next;
13     }
14 public: int KMP(int *next,string S,string T){
15         int i=0,j=0;
16         while(i<S.length()){
17             while(j&&S[i]!=T[j]) j=next[j];
18             if(S[i]==T[j]) j++;
19             i++;
20         }
21         return j;
22     }
23 public: string shortestPalindrome(string s) {
24         
25         string t="";
26         for(int i=s.length()-1;i>=0;i--) t+=s[i];
27         
28         int *next=new int[s.length()];
29         next=buildNext(s);
30         
31         int add=s.length()-KMP(next,t,s);
32 
33         string ans="";
34         int i=s.length()-1;
35         while(add--){
36             ans+=s[i];
37             i--;
38             if(i<0) break;
39         }
40         ans+=s;
41         
42         return ans;
43     }
44 };