posted on 2022-10-22 15:46:31 | under 题解 | source
problem
字符串 \(S\) 长为 \(n\)，对于每个前缀，求能盖出这个前缀的最小的印章长度。
solution
令 \(fail_i\) 为 KMP 的最长的 Border 的长度。考虑其定义，那么 \([1,fail_i]=(i-fail_i,n]\)，且这是一段前缀。
令 \(f_i\) 表示能盖出前缀 \(i\) 的最短的印章，令 \(las_i\) 表示前缀 \(i\) 作为印章能盖得最远的地方（另一个定义：\(\max_i[f_{las_i}=i]\cdot i\)），令 \(ans_i\) 表示有多少个印章能盖出前缀 \(i\)。
注意：如果印章 \(i\) 能盖出一段前缀，则这个印章是这段前缀的 Border。
开始转移，从 \(fail_i\) 那里，如果 \(las_{f_{fail_i}}\in(i-fail_i,i)\) 那么可以转移。相当于，\([1,las_{f_{fail_i}}]\) 这一段可以被 \(f_{fail_i}\) 盖出，由定义得 \([1,fail_i]=(i-fail_i,i]\) 亦能被 \(f_{fail_i}\) 盖出。这两部分重叠，所以 \([1,i]\) 可以被 \(f_{fail_i}\) 盖出。
直接转移即可。
code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
void kmp(char *s,int fail[]){
int n=strlen(s+1); fail[1]=0;
for(int i=2,j=0;i<=n;i++){
while(j&&s[j+1]!=s[i]) j=fail[j];
j+=s[j+1]==s[i];
fail[i]=j;
}
}
int n,f[500010],las[500010],fail[500010];
char s[500010];
int dp(){
for(int i=1;i<=n;i++){
f[i]=i;
if(las[f[fail[i]]]>=i-fail[i]) f[i]=f[fail[i]];
las[f[i]]=i;
}
return f[n];
}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%s",s+1),n=strlen(s+1),kmp(s,fail),printf("%d\n",dp());
return 0;
}