2021.11.09 P3426 [POI2005]SZA-Template（KMP+DP）
https://www.luogu.com.cn/problem/P3426
题意：
你打算在纸上印一串字母。
为了完成这项工作，你决定刻一个印章。印章每使用一次，就会将印章上的所有字母印到纸上。
同一个位置的相同字符可以印多次。例如：用 aba 这个印章可以完成印制 ababa 的工作（中间的 a 被印了两次）。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。例如：用 aba 这个印章不可以完成印制 abcba 的工作。
因为刻印章是一个不太容易的工作，你希望印章的字符串长度尽可能小。
分析：
nexti是求前缀的 前缀及后缀 的最长公共前缀，0~nexti[i]和i-nexti[i]+1~i这两段字符是完全相同的，如果i-nexti[i]+1<=nexti[i]那么说明这两段可以完美融合~f[i]为到i位需要的最小的印章数，vis[f[i]]是到第i位用的印章数最长能盖到哪儿，如果能直接盖过中间不属于前后两个公共前缀的地方，那就可以完美覆盖。
代码如下：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+10;
int nexti[N],f[N],vis[N];
char s[N];
inline void getnext(char *s){
int n=strlen(s);
int k=-1;nexti[0]=-1;
for(int i=0;i<n;){
while(s[i]!=s[k]&&k!=-1)k=nexti[k];
if(s[i]==s[k]||k==-1)nexti[++i]=++k;
}
//for(int i=1;i<=n;i++)cout<<nexti[i]<<" ";cout<<endl;
}
int main(){
scanf("%s",s);
getnext(s);
f[1]=1;vis[1]=1;
int n=strlen(s);
for(int i=2;i<=n;i++){
f[i]=i;
if(vis[f[nexti[i]]]>=i-nexti[i])f[i]=f[nexti[i]];
vis[f[i]]=i;
}
cout<<f[n];
return 0;
}
