[leetcode] 5. 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.

 

풀이

문자열 내에서 Palindrome을 찾는 알고리즘으로 Manacher's Algorithm이 있다.

이를 이용하여 $O(n)$의 시간복잡도로 원하는 답을 찾을 수 있다.

 

Time Complexity : $O(n)$

 

코드

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length()==0)return s;
        string sm;
        sm.push_back('$');
        for(int i=0;i<s.length();i++)
        {
            sm.push_back(s[i]);
            sm.push_back('$');
        }
        
        int r=0,p=0,l=sm.length(), ans=0, ansind;
        vector<int> a(l);
        for (int i=0;i<l;i++)
        {
            a[i] = i<=r?min(a[2*p-i],r-i):0;
            while (i-a[i]-1 >= 0 && i+a[i]+1 <l && sm[i-a[i]-1] == sm[i+a[i]+1]) a[i]++;
            if (r < i+a[i]) r = i+a[i], p = i;
            if(ans<a[i]) ans=a[i], ansind=i;
        }
        return s.substr((ansind-ans)/2,ans);      

    }
};