Created
September 15, 2018 03:54
-
-
Save zhangxiaomu01/3b3803fee6b706ffdee9098059402d07 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
string preProcess(string s) | |
{ | |
int len = s.size(); | |
string proStr = "^"; | |
//string numberStr = "#"; | |
//string dollarStr = "$"; | |
for(int i = 0; i < len; i++) | |
{ | |
proStr.push_back('#'); | |
proStr.push_back(s[i]); | |
} | |
proStr.push_back('#'); | |
proStr.push_back('$'); | |
return proStr; | |
} | |
string longestPalindrome(string s) { | |
int len = s.size(); | |
if(len == 0) | |
return s; | |
string pS = preProcess(s); | |
int len_pS = pS.size(); | |
int C = 0, R = 0, i_mirror = 0; | |
int arr[len_pS]; | |
for(int i = 0; i < len_pS; i++) | |
{ | |
i_mirror = 2 * C - i; | |
if(i < R) | |
{ | |
arr[i] = min(R - i, arr[i_mirror]); | |
} | |
else | |
{ | |
arr[i] = 0; | |
} | |
while(pS[i+1 + arr[i]] == pS[i - 1 - arr[i]]) | |
{ | |
arr[i]++; | |
} | |
if(i + arr[i] > R) | |
{ | |
C = i; | |
R = i + arr[i]; | |
} | |
} | |
int maxLen = 0, start = 0; | |
for(int i = 0; i < len_pS; i++) | |
{ | |
if(arr[i]>maxLen){ | |
maxLen = arr[i]; | |
start = i; | |
} | |
} | |
start = (start - maxLen)/2; | |
return s.substr(start, maxLen); | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment