P3546 [POI2012] PRE-Prefixuffix

Alex_Wei · 2021-12-19 22:52:09 · 题解

Upd on 2022.9.4：修改表述。

*P3546 [POI2012] PRE-Prefixuffix

POI 合集。

好题。

若 S, T 循环相同，则它们可以被写成 AB 和 BA 的形式。因此，对 s 的每个 border 长 i (2i\leq S)，求 s[i + 1, n - i] 最长的不重叠 border 长 f_i，则 \max i + f_i 即答案。

考虑所有 s_i = s[i + 1, n - i]，s_i 的 border 掐头去尾后变成了 s_{i + 1} 的 border，因此 |B_{\max} (s_i)| \leq |B_{\max} (s_{i + 1})| + 2。

根据这一性质，我们从大到小枚举所有 i (1\leq i\leq n / 2)，维护长度 p 表示 s_i 的最长 不重叠 border 长。当 i\to i - 1 时，令 p\gets p + 2，并不断减小 p 直到 p 是 s_i 的不重叠 border 长。势能分析，p 的移动距离不超过 2n。

判断字符串是否相等使用哈希，自然溢出哈希会被卡。求 s 的所有 border 直接 KMP 即可。时间复杂度线性。双倍经验。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
inline int read() {
  int x = 0;
  char s = getchar();
  while(!isdigit(s)) s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 1e6 + 5;
constexpr int mod = 1e9 + 7;
int n, ans, f[N], nxt[N], hsh[N], pw[N];
int calc(int l, int r) {return l--, (hsh[r] - 1ll * hsh[l] * pw[r - l] % mod + mod) % mod;}
char s[N];
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0);
  cin >> n >> s + 1;
  for(int i = pw[0] = 1; i <= n; i++) pw[i] = 1ll * pw[i - 1] * 131 % mod;
  for(int i = 2, j = 0; i <= n; i++) {
    while(j && s[j + 1] != s[i]) j = nxt[j];
    nxt[i] = j += s[j + 1] == s[i];
  }
  for(int i = 1; i <= n; i++) hsh[i] = (1ll * hsh[i - 1] * 131 + s[i]) % mod;
  for(int i = n / 2; i; i--) {
    f[i] = f[i + 1] + 2;
    while(f[i]) {
      if((i + f[i]) * 2 > n) f[i]--;
      else if(calc(i + 1, i + f[i]) != calc(n - i - f[i] + 1, n - i)) f[i]--;
      else break;
    }
  }
  for(int i = nxt[n]; i; i = nxt[i]) if(i * 2 <= n) ans = max(ans, f[i] + i);
  cout << ans << "\n";
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/9/4
author: Alex_Wei
start coding at 8:40
finish debugging at 8:50
*/