# CodeForces 1326D - Prefix-Suffix Palindrome

hashing字符串

2020-03-20 13:20 CST

## Problem

• 首先将字符串最前面和最后面对称的部分依次加入到答案中
• 然后将中间剩下的部分求最长回文前/后缀加入到答案中即可。

## Solution

#include <iostream>
#include <cstring>
using namespace std;

int n = 0, len = 0;
char s[1000006] = {};
char ans[1000006] = {};

long long base = 71;
long long mod = 1e9+7; // 小心LONG LONG

int getL(int l, int r) {
int ret = l;
long long hl = 0, hr = 0, m = 1;
for (int p = l; p <= r; ++p) {
hl = ((long long)(s[p] - 'a') + base * hr) % mod;
hr = (hl + m * (s[p] - 'a')) % mod;
m = (m * base) % mod;
if (hl == hr) {
ret = p;
}
}
return ret;
}

int getR(int l, int r) {
int ret = r;
long long hl = 0, hr = 0, m = 1;
for (int p = r; p >= l; --p) {
hl = ((long long)(s[p] - 'a') + base * hr) % mod;
hr = (hl + m * (s[p] - 'a')) % mod;
m = (m * base) % mod;
if (hl == hr) {
ret = p;
}
}
return ret;
}

int main() {
int T = 0;
scanf("%d", &T);
while (T--) {
scanf("%s", s);
n = strlen(s), len = 0;
int l = 0, r = n - 1;
while (s[l] == s[r]) {
ans[len++] = s[l];
++l, --r;
}
if (l < r) {
int sl = getL(l, r);
int sr = getR(l, r);
if (sl - l > r - sr) {
for (int p = l; p <= sl; ++p) {
ans[len++] = s[p];
}
} else {
for (int p = sr; p <= r; ++p) {
ans[len++] = s[p];
}
}
}
for (++r; r < n; ++r) {
ans[len++] = s[r];
}
ans[len] = '\0';
printf("%s\n", ans);
}
return 0;
}

<EOF>