Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

C++:
01 class Solution {
02 public:
03     string longestPalindrome(string s) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int n=s.size();
07         int m=2*n1;
08         int length=0;
09         int first=0;
10         for(int i=0;i<m;i++)
11         {
12             if(i%2==0)
13             {
14                 int len=1;
15                 int t=i/2;
16                 if(len>length)
17                 {
18                     length=len;
19                     first=t;
20                 }
21                 int j=t1;
22                 int k=t+1;
23                 while((j>=0)&&(k<n))
24                 {
25                     if(s[j]!=s[k])
26                         break;
27                     len+=2;
28                     if(len>length)
29                     {
30                         length=len;
31                         first=j;
32                     }
33                     j;
34                     k++;
35                 }
36             }
37             else
38             {
39                 int len=0;
40                 int j=i/2;
41                 int k=j+1;
42                 while((j>=0)&&(k<n))
43                 {
44                     if(s[j]!=s[k])
45                         break;
46                     len+=2;
47                     if(len>length)
48                     {
49                         length=len;
50                         first=j;
51                     }
52                     j;
53                     k++;
54                 }
55             }
56         }
57         return s.substr(first,length);
58     }
59 };
Advertisements
This entry was posted in Array and linked list, 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