题解：CF1326D1 Prefix-Suffix Palindrome (Easy version)

· · 题解

写在前面

本来板刷 1800 先写的 hard version，拼尽全力只能想出 O(n^2) 的暴力解法，遂先把这题过了。

思路

本题实质上是求解一个字符串 s 的某个前缀 a 和前缀 b 所能组成的最长回文串 t，手玩样例不难发现 t 的组成无外乎三种情况：

  2. 只由 a 组成，且 a 回文。
  3. 只由 b 组成，且 b 回文。

于是解法就很明朗了，首先找出原字符串 s 最长的 a 和 b，这里用双指针或者翻转 s 后遍历都行。然后找出除 a 和 b 的最长回文子串，这里只需要边遍历边 check 即可，check 函数就是常规的判断回文串函数，于是就可以愉快的通过该题啦（然后卡死在 hard version）。

AC 代码

#include <bits/stdc++.h>
using namespace std;
bool check (const string& s) {
    int n = s.size();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) return false;
    }
    return true;
}
void F1ower() {
    string s;
    cin >> s;
    int n = s.size();
    string t = s;
    reverse(t.begin(), t.end());
    int ini = 0;
    string res;
    for (int i = 0; i < n; i++) {
        if (s[i] != t[i]) break;
        ini++;
        res += s[i];
    }
    string plus;
    string temp;
    for (int i = ini; i < n - ini; i++) {
        temp += s[i];
        if (check(temp) && temp.size() > plus.size()) {
            plus = temp;
        }
    }
    string temp2;
    for (int i = n - ini - 1; i >= ini; i--) {
        temp2 += s[i];
        if (check(temp2) && temp2.size() > plus.size()) {
            plus = temp2;
        }
    }
    string ans = res + plus;
    for (int i = n - ini; i < n; i++) ans += s[i];
    cout << (ans.size() > n ? s : ans) << "\n";
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        F1ower();
    }
    return 0;     
}