一道思维难度较高的 KMP 题目,对 border 性质要求较高。
Description
给定一个字符串 $s$, 求长度最小的前缀 $t$ 满足"匹配"完 $s$,这里的"匹配"可以看原题目,不太好描述,建议根据样例手玩一下。
Solution 1
考虑 fail 树。$n$ 为 $s$ 的长度。
我们发现一个前缀 $t$ 能够满足题目要求"匹配", 则它必然是 $s$ 的 border。 同时还要满足所有 border 为它的位置之间距离最大值小于等于 $t$ 的长度。
那么我们可以从小到大枚举 $s$ 的 border, 即从根往节点 $n$ 走, 每次删除当前节点的子树, 用双向链表维护距离最大值。
Code 1
#include<bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();} while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();} return x * f; } const int N = 5e5 + 10; int n, mx, nxt[N], pre[N], suf[N], to[N]; char s[N]; vector<int> E[N]; inline void chmax(int &x, int y) {x = max(x, y);} inline void del(int x) { if (x) { int tp = pre[x], ts = suf[x]; chmax(mx, ts - tp); suf[tp] = ts; pre[ts] = tp; } for (auto v : E[x]) if (v != to[x]) del(v); } int main () { scanf("%s", s + 1); n = strlen(s + 1); nxt[1] = 0; for (int i = 2, j = 0; i <= n; ++ i) { while (j && s[i] != s[j+1]) j = nxt[j]; if (s[i] == s[j+1]) ++ j; nxt[i] = j; } for (int i = 1; i <= n; ++ i) E[nxt[i]].push_back(i); for (int i = n; i; i = nxt[i]) to[nxt[i]] = i; for (int i = 1; i <= n; ++ i) pre[i] = i - 1, suf[i] = i + 1; del(0); int ans = 1; while (mx > ans) del(ans), ans = to[ans]; printf("%d\n", ans); return 0; }View Code
Solution 2
考虑 DP。用 $dp_i$ 表示长度为 $i$ 的 $s$ 的前缀的答案。
有一个很奇妙的性质就是 $dp_i$ 只可能有两种取值, $i$ 或者 $dp_{nxt_i}$。
感性上证明一下。设 $t$ 为当前的前缀, $p$ 为 $t$ 的最长border。
能够"匹配" $t$ 的必要条件就是能够与 $t$ 相同或者能够和 $p$ "匹配"。因为除了 $t$ 本身以外, 最长的可能匹配串就是 $p$, 而只有能够匹配 $p$,才能和 $t$ 匹配 。
那么什么时候 $dp_i$ 能取到 $dp_{nxt_i}$ 呢?我们显然能够"匹配"到长度为 $nxt_{i}$的前缀和后缀,因此我们只要找到长度 $nxt_i$的前缀能够匹配最远的距离 $j$, 满足 $i - nxt_i \leq j$ 即可。
Code 2
#include<bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();} while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();} return x * f; } const int N = 5e5 + 10; int n, nxt[N], dp[N], vis[N]; char s[N]; int main () { scanf("%s", s + 1); n = strlen(s + 1); nxt[1] = 0; for (int i = 2, j = 0; i <= n; ++ i) { while (j && s[i] != s[j+1]) j = nxt[j]; if (s[i] == s[j+1]) ++ j; nxt[i] = j; } dp[1] = 1; vis[1] = 1; for (int i = 2; i <= n; ++ i) { dp[i] = i; if (vis[dp[nxt[i]]] >= i - nxt[i]) dp[i] = dp[nxt[i]]; vis[dp[i]] = i; } printf("%d\n", dp[n]); return 0; }View Code
标签:nxt,匹配,前缀,POI2005,SZA,int,Template,ans,dp From: https://www.cnblogs.com/CikL1099/p/17036874.html