D2. Prefix-Suffix Palindrome (Hard version)

Link

Solution

一道比较有意思的字符串题，在给定字符串s中找出一对没有重叠部分的前缀和后缀使得前后缀拼起来是一个回文串并输出最长的结果。

可以将原串分成三个部分A、B和C，其中A是原串前缀的一部分，C是原串后缀的一部分，要满足条件的话A肯定等于reverse(C)，而对于B可以找出B的最长回文前缀和最长回文后缀，其中最长回文后缀就是reverse(B)的最长回文前缀，这样用一个函数就可以解决，最后取二者较长的那个接在A和C中间就是答案。

至于longestPalindromePrefix()的具体实现，对一个字符串求其最长回文前缀可以先将原串和反串用一个特殊字符连接起来，然后对新串求前缀函数即可。

Code

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using LL = long long;
constexpr int maxn = 2e6 + 10;

int pre[maxn];

string longestPalindromePrefix(const string& s) {
    string a = s;
    reverse(a.begin(), a.end());
    a = s + "#" + a;
    int k = 0;
    for (int i = 1; i < a.size(); i++) {
        while (k&& a[k] != a[i])k = pre[k - 1];
        if (a[k] == a[i])k++;
        pre[i] = k;
    }
    return s.substr(0, k);
}

int main(int argc, char **argv) {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int len = 0;
        while (len < s.size() - len - 1) {
            if (s[len] != s[s.size() - len - 1])break;
            len++;
        }
        if (len > 0)cout << s.substr(0, len);
        if (s.size() > 2 * len) {
            string tmp = s.substr(len, s.size() - 2 * len);
            string a = longestPalindromePrefix(tmp);
            reverse(tmp.begin(), tmp.end());
            string b = longestPalindromePrefix(tmp);
            if (a.size() < b.size())swap(a, b);
            cout << a;
        }
        if (len > 0)cout << s.substr(s.size() - len, len);
        cout << endl;
    }
    return 0;
}