Luogu P3426 [POI2005]SZA-Template

题目描述

https://www.luogu.com.cn/problem/P3426

简要题意：给定一个字符串 $S$，例如有一个 $aba$ 的印章，我们可以用这个印章完成 $ababa$ 的印刷，中间的 $a$ 被印了两次，但是同一位置上印不同字符是不行，求一个长度最小的印章

$n\le 5\times 10^5$

Solution

我们考虑先用 $KMP$ 求出 $fail$ 树，容易发现印章上的字符只有可能是 $n$ 到根上的所有点 $u$，且点 $u$ 合法的条件是子树内出现的点的最大间距不超过 $u$

那么我们考虑从根向 $n$ 进行 $dfs$，每次只保留子树内的点，同时维护最大间距，因为只有删点，所以可以使用双向链表做到 $O(1)$ 删点

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define maxn 500010
using namespace std;

int nxt[maxn]; 
void init_nxt(char *s) {
    int k = 0, n = strlen(s + 1); nxt[1] = 0;
    for (int i = 2; i <= n; ++i) {
        while (k && s[k + 1] != s[i]) k = nxt[k];
        if (s[k + 1] == s[i]) ++k;
        nxt[i] = k;
    }
}

struct Edge {
    int to, next; 
} e[maxn]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
    
int n;
char s[maxn];

int l[maxn], r[maxn], Max;
void del(int x) {
    r[l[x]] = r[x];
    l[r[x]] = l[x];
    Max = max(Max, r[x] - l[x]); 
}

void dfs(int u, int t) {
    if (u) del(u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == t) continue;
        dfs(e[i].to, t);
    }
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1; n = strlen(s + 1); init_nxt(s);
    for (int i = 1; i <= n; ++i) add_edge(nxt[i], i);
    vector<int> A; 
    for (int i = n; i; i = nxt[i]) A.push_back(i);
    A.push_back(0); reverse(A.begin(), A.end()); int ans = n;
    for (int i = 1; i <= n; ++i) l[i] = i - 1, r[i] = i + 1; 
    for (int i = 1; i < A.size(); ++i) {
        dfs(A[i - 1], A[i]);
        if (Max <= A[i]) ans = min(ans, A[i]);
    } cout << ans << "\n";
    return 0; 
}