循环同构串 string

PS：如果读过题了可以跳过题目描述直接到题解部分
暂无提交链接

题目

题目背景

因为题目简单，同学们开开心心地研究起了字符串的性质。

题目描述

如果将字符串 S = s 1 ， s 2 … s n S=s_1，s_2…s_n S=s1​，s2​…sn​ 的所有字符左移一位，然后让第一位字符移动到最后一位，即构成新的字符串： S ′ = s 2 ， s 3 … s n ， s 1 S'=s_2，s_3…s_n，s_1 S′=s2​，s3​…sn​，s1​。这个操作称为字符串的左移。
比如字符串orz左移一次得到字符串rzo。
若$S$串能够通过若干次左移之后变成$T$串，我们就称$S$和$T$循环同构，
现在给你一个长度为$n$的字符串$S$，询问字符串$S$是否满足以下条件：

1. 存在一个整数$k>1$，满足$k$是$n$的因数。
2. 将$S$分成$k$段子串，每段等长，长度为 n k \frac{n}{k} kn​。
3. 存在一个字符串$T$，与上述的$k$段子串都循环同构。

如果存在$k,T$满足上述三个条件，那么就输出 Yes，否则输出 No。

输入格式

一行，一个整数$t$，表示有$t$组数据。
对于每组数据，输入两行：
第一行，一个整数$n$，表示字符串长度。
第二行，一个长度为$n$的字符串。

输出格式

对于每组数据，输出对应的 Yes 或者 No

样例

输入

6
1
a
2
aa
3
aab
4
abba
6
abcbcc
8
aaaaaaaa

输出

No
Yes
No
Yes
No
Yes

提示

数据范围

对 20%的数据满足，$n\le 100$
对 40%的数据满足，$n\le 1000$
对 100%的数据满足， n ≤ 5 ∗ 1 0 6 , t ≤ 20 n\le5*10^6,t\le20 n≤5∗106,t≤20
字符串仅由小写字母组成。

题解

最大公因数

一开始我不太会打KMP，所以就直接用最大公因数来判断理论上的最多只能分成几段，如果最多只能分成一段，那显然应该输出 No。但判断Yes必须要使用KMP。

暴力KMP

改题的时候我还是保留了我一开始最大公因数判断的部分，这样在考虑分段情况的时候可以减少一些情况。
做KMP的时候把分出来的第一段当成目标串，标记nex数组，把后面每一段翻成两倍，作为主串。如果在一种分段情况下成立，就可以直接输出 Yes，然后进行下一个字符串的判断（即不用考虑剩下的分段情况），反之则需要进行下一种分段的判断（即不用判断后面几段）。

代码实现

//循环同构串 string
#pragma GCC optimize(3)
#include
#include
#include
using namespace std;
int t;
int n;
char a[5000010];
bool b;
int p[5000010];
int c[30];
char d[5000010];
int nex[5000010];int gcd(int x,int y){if(y==0){return x;}return gcd(y,x%y);
}int main(){register int i,j,k,l,m;scanf("%d",&t);while(t--){b=0;memset(c,0,sizeof(c));scanf("%d\n",&n);for(i=1;i<=n;++i){a[i]=getchar();++c[a[i]-'a'];}j=n;for(i=0;i<26;++i){if(c[i]){j=min(j,gcd(n,c[i]));if(j==1){b=1;break;}}}if(b){printf("No\n");continue;}for(j;j>1;--j){if(n%j==0){b=0;l=n/j;i=1;k=0;nex[1]=0;while(i<=l){if(k==0||a[i]==a[k]){++i;++k;nex[i]=k;}else{k=nex[k];}}for(i=1;i<=j-1;++i){for(k=i*l+1;k<=l*(i+1);++k){d[k-i*l]=d[k-(i-1)*l]=a[k];}k=1,m=1;while(k<=l&&m<=l*2){if(k==0||a[k]==d[m]){++m;++k;}else{k=nex[k];}}if(k<l){b=1;break;}}if(!b){break;}}}if(!b){printf("Yes\n");}else{printf("No\n");}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！