Longest palindromic contiguous substring

Given a string, find the longest palindromic contiguous substring. If there are more than one with the maximum length, return anyone.

For example, the longest palindromic substring of "aabcdcb" is "bcdcb". The longest palindromic substring of "bananas" is "anana".

Example:

Input:  s = "aabcdcb"
Output: bcdcb

Approach

C++

#include <bits/stdc++.h>
using namespace std;

#define SIZE 200000 + 1
long long P[SIZE * 2];
string newstring(string s)
{
    string str = "@";

    for (long long i = 0i < s.size(); i++)
    {
        str += "#" + s.substr(i1);
    }

    str += "#$";
    return str;
}

string longestPalindromicSubstring(string s)
{
    string str = newstring(s);
    long long c = 0r = 0;
    for (long long i = 1i < str.size() - 1i++)
    {
        long long imirror = c - (i - c);
        if (r > i)
            P[i] = min(r - iP[imirror]);
        while (str[i + 1 + P[i]] == str[i - 1 - P[i]])
            P[i]++;
        if (i + P[i] > r)
        {
            r = i + P[i];
            c = i;
        }
    }
    long long len = 0;
    long long center = 0;
    for (long long i = 1i < str.size() - 1i++)
    {
        if (P[i] > len)
        {
            len = P[i];
            center = i;
        }
    }

    string ans = s.substr((center - 1 - len) / 2len);

    return ans;
}
int main()
{
    string s = "aabcdcb";

    cout << longestPalindromicSubstring(s);

    return 0;
}


No comments:

Post a Comment