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

Posted on In Disqus:

题目

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

题意

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

题解

  • 用 Z 算法求出 s 与每个后缀的 LCP 记为 z[x]。
  • 暴力枚举长度 l，判断是否满足 z[n − l + 1] = l 且 ∃i ∈ [l + 1, n − 2l + 1] : z[i] ≥ 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;
}