题意：
给定一个字符串，求能盖出这个字符串的印章的最小长度。
分析：
显然，这个印章一定是 \(s\) 的 border。
记 \(dp_{i}\) 表示盖满前 \(i\) 个的最小印章大小，那么答案只可能为 \(i\)，或者 \(dp_{kmp_{i}}\)。
证明如下：
- 显然答案为 \(i\) 是整个字符串。
- 由于 \(s\) 的 border 可以拆分成两部分，即 \(t\) 的 border 与 \(t\) 本身，\(dp_{kmp_{i}}\) 均有。
现在只剩一个问题，什么时候 \(dp_{i}=dp_{kmp_{i}}\) 成立呢？
对于两个相交的串 \(A,B\)，如果它们均能被 \(t\) 盖出，那么 \(A \cup B\) 一定能被 \(t\) 盖出。因为印章只可能为 \(A \cap B\)，因此一定能盖出\(A \cup B\)。
由于 \(dp_{kmp_{i}}\) 能盖出 \([1...kmp_{i}]\)，那么它也一定能盖出 \([i-kmp_{i}+1,i]\)，于是如果 \(dp_{kmp_{i}}\) 最远能盖到 \(i-kmp_{i}\) 及以后，那么就一定能盖完 \([1...i]\)。
于是我们再记 \(h_{i}\) 表示前缀 \(i\) 作为印章时最远能盖到的位置，然后直接转移即可。
代码：
#include<bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
int n;
int kmp[N], dp[N], h[N];
string s;
signed main() {
cin >> s;
n = s.length();
s = " " + s;
int j = 0;
for(int i = 2; i <= n; i++) {
while(j && (s[j + 1] != s[i])) j = kmp[j];
if(s[j + 1] == s[i]) j++;
kmp[i] = j;
}
for(int i = 1; i <= n; i++) {
dp[i] = i;
if(h[dp[kmp[i]]] >= i - kmp[i]) dp[i] = dp[kmp[i]];
h[dp[i]] = i;
}
cout << dp[n];
return 0;
}