自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:50:03，当前版本为作者最后更新于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
*/