Longest palindromic sub-string

Given a string S, find the longest palindromic sub-string in S.

C++:
01 string preprocess(string s)
02 {
03     string t=“#”;
04     if(s.length()==0)
05         return t;
06     t+=s.at(0);
07     return t+preprocess(s.substr(1));
08 }
09 
10 string postprocess(string s)
11 {
12     string t;
13     for(int i=0;i<s.length();i++){
14         if(s.at(i)!=‘#’)
15             t+=s.at(i);
16     }
17     return t;
18 }
19 
20 string longestPalin(string s)
21 {
22     string w=preprocess(s);
23     int n=w.length();
24     int *A=new int[n];
25     int C=0;
26     int R=0;
27     for(int i=0;i<n;i++)
28         A[i]=0;
29     for(int i=0;i<n;i++){
30         int m=2*Ci;
31         if((m>=0)&&(A[m]+i<R))
32             A[i]=A[m];
33         else{
34             C=i;
35             int j=R+1;
36             while((j<n)&&(2*ij>=0)){
37                 if(w[j]==w[2*ij]){
38                     R=j;
39                     j++;
40                 }else
41                     break;
42             }
43             A[i]=Ri;
44         }
45     }
46     int max_len=0;
47     int max_index=0;
48     for(int i=0;i<n;i++){
49         if(A[i]>max_len){
50             max_len=A[i];
51             max_index=i;
52         }
53     }
54     string t=w.substr(max_indexmax_len,2*max_len);
55     return postprocess(t);
56 }
Advertisements
This entry was posted in String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s