0005-Longest-Palindromic-Substring
Problem Description
Given a string s, return the longest palindromic substring in s.
Solution
string longestPalindrome(string s0) {
std::string s = "#";
for (char c : s0) {
s += c;
s += "#";
}
int l = 0;
int r = 0;
int n = s.size();
int max_pos = 0;
vector<int> lps(n);
for (int i = 0; i < n; ++i) {
if (i <= r) {
lps[i] = min(lps[l + (r - i)], r - i);
}
while (i - lps[i] - 1 >= 0 && i + lps[i] + 1 < n &&
s[i - lps[i] - 1] == s[i + lps[i] + 1]) {
++lps[i];
l = i - lps[i];
r = i + lps[i];
}
if (lps[i] > lps[max_pos]) {
max_pos = i;
}
}
return s0.substr((max_pos - lps[max_pos]) / 2, lps[max_pos]);
}