【题解】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\)。
• 范围具有单调性，维护一下最大值。

代码

#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;
}