标签：POI2005 SZA ne int 2453301 Template mx
- 本想尝试一下朴素算法能得多少分，没想到直接过了……亲手构造了n=80000的全a数据，确定程序的复杂度的确是错的
- 考虑通过KMP算法构建的“失配树”，大概可以用双向链表维护前驱后继
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int ne[500005],n;
bool pd(int j)
{
int mx=j;
for(int i=j+1;i<=n;i++)
{
if(ne[i]>=j)
{
mx=i;
}
else if(i-mx==j)
{
return false;
}
}
return mx==n;
}
int main()
{
string s;
cin>>s;
n=s.size();
ne[1]=0;
for(int i=2;i<=n;i++)
{
int j=ne[i-1];
while(j!=0&&s[j]!=s[i-1])
{
j=ne[j];
}
if(s[j]==s[i-1])
{
j++;
}
ne[i]=j;
}
/*
for(int i=1;i<=n;i++)
{
cout.width(3);
cout<<ne[i];
}
cout<<endl;
for(int i=1;i<=n;i++)
{
cout.width(3);
cout<<i;
}
cout<<endl;
*/
int ans=n;
int j=ne[n];
while(j!=0)
{
if(pd(j)==true)
{
ans=j;
}
j=ne[j];
}
cout<<ans<<endl;
return 0;
}
标签：POI2005,
SZA,
ne,
int,
2453301,
Template,
mx
From： https://www.cnblogs.com/watersail/p/18001678