字符串最短循环节

2024-07-10 22:35| 来源: 网络整理| 查看: 265

循环节与最短循环节：若某个字符串是由某个子串循环构成的，那么就称该子串为原串的循环节，长度最短的循环节就是最短循环节。如abababab，abab和ab都是原串的循环节，而最短循环节是ab。

结论：如果字符串 s 有个循环节 son，n = |s| , x = |son|，字符数组下标从1开始，那么：

x 一定是 n 的约数。那么s[1,n-x] = s[x, n] = son。

证明：结论1：如果 x 不是 n 的约数，那么自然 n 就不可能由若干个 x 相加构成，即不满足 n = k * x ，其中 k 是正整数。结论2：若想s[1 ,n-x] = s[x, n] ，必须s[1, x] = s[ x ,2x] = s[2x , 3x] = … = s[n-x , n]，刚好符合循环节定义，因此结论2 成立。

求单个字符串的最短循环节

例1： POJ 2406 Power Strings (KMP) 测试地址题意简述：给定一个字符串 s ，求出它最多由某个子串循环几次构成。

解题思路：首先 s 必须是由某个循环节循环若干次构成的，否则无解。题意让求最多循环几次构成，那么既然 s 的长度固定是 n，自然是循环节越短，那么循环次数越多了。我们先求出KMP算法中的nex数组。结论3：此时若 s 有解，那么最短循环节长度为 x = n - nex[n] 。

证明：反证法

首先根据结论2，因为 s[1,nex[n] ] = s[n - nex[n] , n]，所以必然存在长度为 x = n - nex[n]的循环节，问题就在于它是不是最短的。假设存在循环节，长度为 y（y < x），那么根据结论2，一定有： s[1, n-y] = s[y , n]；如此一来nex[n] = n-y > n-x，这和nex数组定义矛盾，因此不存在y < x。综上所述，n - nex[n] 一定为最短循环节的长度。

因此本题的答案就是 n/(n-nex[n])，若不能整除，则无解。

代码示例：见附录部分 code-1：Power Strings

求任意子串的最短循环节

例2： bzoj2795 Horrible Poem 测试地址题意简述：给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节长度。如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。

解题思路：此题的 q 很大，我们不可能对每一个子串都O(n)求出 nex 数组再回答。我们利用滚动哈希，在O(1)时间内利用结论2 判断某个长度是否为循环节。再根据结论1，可以得知循环节长度一定是子串长度 m 的约数，因此我们 O ( m ) O(\sqrt m) O(m )分解约数，再用O(1)复杂度用hash判断，本题总复杂度就是 O ( q m ) O(q \sqrt m) O(qm )。

一般到这里就该结束了，我们利用了结论1 和结论2 大大减少了求循环节的时间。但是在本题还是不够，还需要优化。还能优化的地方就只有求约数的 O ( m ) O(\sqrt m) O(m )复杂度了，我们可以通过质因数分解在 O ( l o g 2 m ) O(log_2^m) O(log2m)时间内分解约数，于是最终复杂度就是 O ( q l o g 2 n ) O(q\:log_2^n) O(qlog2n)，可以通过了。

代码示例：见附录部分code-2：Horrible Poem

附录

code-1：Power Strings

#include #include #include using namespace std; const int N = 1e6+10; char str[N]; int nex[N]; void getNex(char* str){ memset(nex,0,sizeof nex); for(int i = 2,j = 0;str[i];i++){ while(j > 0 && str[i] != str[j+1]) j = nex[j]; if(str[i] == str[j+1]) j++; nex[i] = j; } } void solve(){ /*计算答案并输出*/ getNex(str); int n = strlen(str)-1; if(n%(n-nex[n])) puts("1"); else printf("%d\n",n/(n-nex[n])); } int main(){ while(scanf("%s",str+1) && str[1] != '.'){ str[0] = '*'; solve(); } return 0; }

code-2：Horrible Poem

#include #include #include using namespace std; const int N = 5e5+10; const int Q = 2e6+10; char str[N]; int n,q; typedef unsigned long long ull; ull hsh[N],bse[N] , b = 31; //采用无符号长整形,通过自然溢出省去取模 bool check(int l,int r,int x){ /*判断x是否为子串s[l,r]的最短循环节长度*/ ull h1 = hsh[r-x] - hsh[l-1]*bse[r-x+1-l]; ull h2 = hsh[r] - hsh[l-1+x]*bse[r-x+1-l]; return h1 == h2; } int v[N],primes[N]; void getPri(){ //线性筛 int cnt = 0; for(int i = 2;i N) break; v[i*primes[j]] = primes[j]; } } } void ask(int l,int r){ /*回答子串s[l,r]的最短循环节长度*/ int len = r-l+1, ans = len, d = len; while(d != 1){ int tmp = v[d]; while(d%tmp == 0 && check(l,r,ans/tmp)) d /= tmp,ans /= tmp; while(d%tmp == 0) d /= tmp; } printf("%d\n",ans); } void solve(){ /*预处理出hash数组,v数组*/ getPri(); bse[0] = 1; for(int i = 1;i ='0'&&c

【本文地址】

字符串最短循环节

字符串最短循环节

今日新闻

推荐新闻