Longest Palindromic Substring(LeetCode)

| Tags LeetCode  Algorithm 
 1 #include <string>
 2 #include <iostream>
 3 using namespace std;
 4 
 5 string longestPalindrome(string s)
 6 {
 7     // Start typing your C/C++ solution below
 8     // DO NOT write int main() function
 9 
10  int size = s.size();
11  char *str = new char[size*2+3];
12  str[0] = '$';
13  str[1] = '#';
14  str[size*2+2] = 0;
15  for(int i = 0; i < size; ++i)
16  {
17      str[2*i+2] = s[i];
18      str[2*i+3] = '#';
19  }
20 
21  int *p = new int[size*2+2];
22  memset(p, 0, sizeof(int)*(size*2+2));
23  p[0] = 1;
24  int mid = 0;
25  int mx = 1;
26  int maxi = 0;
27  int maxlen = 1;
28  for(int i = 1; str[i]; ++i)
29  {
30      if(mx > i)
31          p[i] = min(p[2*mid-i], mx-i);
32      else
33          p[i] = 1;
34 
35      while(str[i-p[i]] == str[i+p[i]])
36          p[i]++;
37 
38      if(mx < i+p[i])
39      {
40          mx = i + p[i];
41          mid = i;
42      }
43 
44      if(maxlen < p[i])
45      {
46          maxlen = p[i];
47          maxi = i;
48      }
49  }
50 
51  delete str;
52  delete p;
53 
54  return s.substr((maxi-maxlen+1)/2, maxlen-1);
55 }
56 
57 int main()
58 {
59  string s;
60  while(true)
61  {
62      cin >> s;
63      cout << longestPalindrome(s) << '\n';
64  }
65 }

Previous     Next