充分暴露出对 \(border\) 结合 \(dp\) 理解的不足。
先来推结论，一个字符串的印章一定是其 \(border\)，因为只有这样才可能兼顾首尾，但是他的 \(border\) 不一定是其印章，两个条件不能互推。
设 \(dp_i\) 表示前 \(i\) 个字符串的最小印章长度。现在考虑如何转移。
\(dp_i\) 的取值只有可能是 \(i\) 和 \(dp_{fail_i}\)，\(i\) 就是取自己为印章，\(dp_{fail_i}\) 表示先将其 \(border\) 想办法填出来，然后再在末尾加上剩余字符。
那么什么时候能从 \(dp_{fail_i}\) 转移过来呢，首先找到一个最大的
\(dp_j=dp_{fail_i}\)，由于在 \(j\) 后面我们至多填上 \(dp_{fail_i}\) 长度的字符串，所以当 \(i-j\le dp_{fail_i}\) 时，可以转移。对于合法的 \(j\)，维护一个 \(dp\) 值对应的最大下标即可。
点击查看代码
const int N=5e5+10;
string s;
int n;
int fail[N];
int maxp[N],dp[N];
int main() {
cin>>s;
n=s.size(); s=" "+s;
for(int i=2;i<=n;i++) {
int j=fail[i-1];
while(s[j+1]!=s[i]&&j) j=fail[j];
if(s[j+1]==s[i]) fail[i]=j+1;
}
for(int i=1;i<=n;i++) {
dp[i]=i;
maxp[dp[i]]=i;
if(!dp[fail[i]]) continue;
if(i-maxp[dp[fail[i]]]<=dp[fail[i]]) {
dp[i]=dp[fail[i]];
maxp[dp[i]]=i;
}
}
cout<<dp[n];
return 0;
}