【POI补全计划#10 POI2005 SZA】
鉴于我没看懂kczno1巨神的题解，我决定自己来写一个
看题立刻想到KMP，就先把next数组求出来
接下来发现模板串满足三个条件
1.一定是一个前缀
2.结束位置一定是最后一个字符一直沿着next数组走能到达的点
3.这个模板串在原串中的所有出现位置一定能覆盖整个串
于是我们从小到大枚举满足条件2的结束位置，每次判一下能不能覆盖整个串，然后就TLE了
然后猜到一个性质（貌似挺显然的）：
能被更短的前缀完全覆盖的前缀一定不是最短的模板串
这就好办了，只需要每次记录当前能覆盖到什么位置，然后每次枚举覆盖到的位置之后的、满足条件2的结束位置，每次判一下能覆盖到哪就做完了
~~然而我不会算这个复杂度，只知道跑得飞快~~
贴代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=500010;
char str[MAXN];
int fail[MAXN];
struct atom
{
int num;
atom *next;
}*h[MAXN],pool[MAXN];
int top;
int flag[MAXN],arr[MAXN];
int top2,minn;
int main()
{
scanf("%s",str+1);
int len=strlen(str+1),k=0;
for(int i=2;i<=len;++i)
{
while(k!=0&&str[k+1]!=str[i])k=fail[k];
if(str[k+1]==str[i])++k;
fail[i]=k;
}
for(int i=len;i>=1;--i)
{
atom *tmp=&pool[++top];
tmp->num=i;
tmp->next=h[fail[i]];
h[fail[i]]=tmp;
}
for(int k=len;k;k=fail[k])
{
flag[k]=1;
}
for(int i=1;i<=len;++i)
{
if(flag[i])
arr[++top2]=i;
}
for(int k=1;k<=top2;++k)
{
if(arr[k]<=minn)continue;
memset(flag,0,sizeof(flag));
int last=arr[k];
flag[arr[k]]=1;
for(int i=arr[k];i<=len;++i)
{
if(flag[i])
{
for(atom *tmp=h[i];tmp;tmp=tmp->next)
{
flag[tmp->num]=1;
}
last=i;
}
else if(i-last>=arr[k])break;
}
if(last==len)
{
printf("%d\n",arr[k]);
return 0;
}
minn=last;
}
return 0;
}
```
[email protected]:minor bug fixes