【题解】51nod-1286-三段子串

题目

http://www.51nod.com/Challenge/Problem.html#!#problemId=1286

题意

求字符串 \(s\) 的一个最长的 border(最长公共前缀后缀) \(t\),使得它在不重合地出现了至少三次。

题解

  • 用 Z 算法求出 \(s\) 与每个后缀的 LCP 记为 \(z[x]\)
  • 暴力枚举长度 \(l\),判断是否满足 \(z[n-l+1]=l\)\(\exists i\in [l+1,n-2l+1]:z[i]\ge l\)
  • 范围具有单调性,维护一下最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 1E6 + 100;

void get_z(int a[], char s[], int n) {
int l = 0, r = 0; a[0] = n;
FOR (i, 1, n) {
a[i] = i > r ? 0 : min(r - i + 1, a[i - l]);
while (i + a[i] < n && s[a[i]] == s[i + a[i]]) ++a[i];
if (i + a[i] - 1 > r) { l = i; r = i + a[i] - 1; }
}
}

char s[N];
int a[N];
int main() {
scanf("%s", s);
int n = strlen(s);
get_z(a, s, n);
int ans = 0, t = 0;
FORD (d, n / 3, 0) {
if (d == n / 3) FOR (i, d, n - 2 * d + 1) t = max(t, a[i]);
else t = max(t, max(a[d], max(a[n - 2 * d], a[n - 2 * d - 1])));
if (a[n - d] == d && t >= d) ans = max(ans, d);
}
cout << ans << endl;
}
w