B4119 题解

luogu_gza · 2025-01-07 16:26:25 · 题解

考虑暴力模拟，枚举 |T|，那么 T=S[1..|T|]，直接检验即可。

暴力代码就不给了。

众所周知一个 border 等价于一个周期，所以我们处理出 s[1..n] 的最大 border 为 l，然后检查是否满足 (n-l) \mid n 即可。

const int N=1e6+10;
int n,T;
char s[N];
int ne[N];
void main(){
  n=R;
  scanf("%s",s+1);
  for(int i=2,j=0;i<=n;i++)
  {
    while(j&&s[i]!=s[j+1]) j=ne[j];
    if(s[i]==s[j+1]) j++;
    ne[i]=j;
  }
  if(n%(n-ne[n])==0&&ne[n]!=0) puts("Yes");
  else puts("No");
}