2018.09.18 atcoder Best Representation（kmp）

传送门
思路简单不知为何调试了很久。
显然要么分成n个（所有字符相同），要么分成1个（原字符串无循环节），要么分成两个（有长度至少为2的循环节）。
一开始以为可以直接hash搞定。
后来wa了几次之后发现可以轻松举出反例于是弃了hash。
kmp大法好啊，判完循环节之后直接枚举两个子串的断点判是不是前缀与后缀同时满足条件就行了。
代码：

#include<bits/stdc++.h>
#define N 500005
#define mod 1000000007
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
char s[N],t[N];
int n,flag,pre[N],suf[N],ans=0;
void getfail(int *fail,char *s)
{
fail[0]=-1;
int j=0;
for(int i=1;i<n;++i){
while(j&&s[i]!=s[j])j=fail[j];
if(s[i]==s[j])fail[i+1]=++j;
else fail[i+1]=0;
}
}
inline bool checkpre(int pos){return pre[pos]==0||pos%(pos-pre[pos]);}
inline bool checksuf(int pos){return suf[pos]==0||pos%(pos-suf[pos]);}
int main(){
scanf("%s",s),n=strlen(s);
for(int i=0;i<n;++i)t[i]=s[n-i-1];
getfail(pre,s),getfail(suf,t),t[n]='';
flag=checkpre(n)?1:2;
bool f=true;
for(int i=1;i<n;++i)if(s[i]!=s[i-1]){f=false;break;}
if(f)flag=n;
cout<<flag<<'n';
if(flag!=2){cout<<1;return 0;}
for(int i=0;i<n;++i){
int tmp=n-i-1;
if(checkpre(i+1)&&checksuf(tmp))++ans;
}
cout<<ans;
return 0;
}

最后

以上就是高兴篮球为你收集整理的2018.09.18 atcoder Best Representation（kmp）的全部内容，希望文章能够帮你解决2018.09.18 atcoder Best Representation（kmp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。