[Blog] [Docs] [Code] [Slides] [About]

CodeForces 1326D - Prefix-Suffix Palindrome

hashing字符串

2020-03-26 16:37 CST

Problem

求最长回文串$a + b$,其中$a$和$b$分别是字符串$s$的不相交的前、后缀。

学了半天最后WA竟然是因为乘法溢出,我吐了。

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

时间复杂度$O(n)$。

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>