-
Notifications
You must be signed in to change notification settings - Fork 0
/
Code
38 lines (31 loc) · 1.25 KB
/
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
string longestPalindrome(string s) {
int maxRightPalindromeBounder = 0;
int centerRightPalindrome = 0;
int lengthOfLargestPalindrome = 0;
int startOfLargestPalindrome = 0;
string preProcessingStr = "$#";
for (char c : s){
preProcessingStr += c;
preProcessingStr += '#';
}
int preProcessingStrLength = preProcessingStr.length();
vector<int> p(preProcessingStrLength, 0);
for (int i = 1; i < preProcessingStrLength; i++){
if (i < maxRightPalindromeBounder)
p[i] = min(p[centerRightPalindrome*2 - i], maxRightPalindromeBounder - i);
else
p[i] = 1;
while (preProcessingStr[i + p[i]] == preProcessingStr[i - p[i]]){
p[i]++;
}
if (i + p[i] > maxRightPalindromeBounder){
maxRightPalindromeBounder = i + p[i];
centerRightPalindrome = i;
}
if (p[i] > lengthOfLargestPalindrome){
lengthOfLargestPalindrome = p[i];
startOfLargestPalindrome = (i - lengthOfLargestPalindrome) / 2;
}
}
return s.substr(startOfLargestPalindrome, lengthOfLargestPalindrome - 1);
}