定期二进制字符串 [英] Periodic Binary Strings

问题描述

有没有什么有效的算法来检查二进制字符串是否是周期的或不是？

Is there any efficient algorithms to check whether a binary string is periodic or not?

令S是一个二进制串和H是集合S.子串接着S被所述，如果它可以通过连接一个或更多次，在H中的至少一个小时，也可为h获得是周期的！=秒。

Let S be a binary string and H be the set of sub strings of S. Then S is said to be periodic if it can be obtained by concatenating one or more times, at least one h in H, also h != S .

推荐答案

初始字符串S采用长度为LEN。双串（真是我们需要的S +半的S）。搜索发生在一倍字符串SS初始串S，从第二位起步，在莱恩/ 2 + 1。如果这样的occurence存在与位置P结尾，则S是周期性的，周期P - 1

Initial string S with length Len. Double the string (really we need S + half of S). Search for occurrence of initial string S in doubled string SS, beginning from 2nd position, ending at Len/2 + 1. If such occurence exists with position P, then S is periodic with period P - 1.

S = abbaabbaabba LEN = 12 SS = abbaabbaabbaabbaabbaabba

S = abbaabbaabba Len = 12 SS = abbaabbaabbaabbaabbaabba

这是第二次到第7位搜索，S为P =发现5，周期= 4

Searching from 2nd to 7th position, S found at P=5, period = 4

S = abaabaabaabb SS = abaabaabaabbabaabaabaabb

S = abaabaabaabb SS = abaabaabaabbabaabaabaabb

S不发生在SS（除了1和L + 1），无期存在

S doesn't occur in SS (except for 1 and L+1), no period exists

PS 注意因用文卡塔斯评论： 我们需要增加最小可能的周期性单元，它的长度为L / 2为偶数大小的字符串，而L为奇数大小的字符串最大除数（如果长度为质数，字符串不能是周期性的）。简单的分解方法有O（N ^ 1/2）的复杂性，更复杂 - O（N ^ 1/4），所以有时它是值得因式分解长度，避免过长的字符串不必要的比较

P.S. Note due to useful Venkatesh comment: We need to add minimal possible periodic unit, it's length is L/2 for even-size strings, and maximum divisor of L for odd-size strings (if length is prime number, string cannot be periodic). Simple factorization methods have O(N^1/2) complexity, more complex - O(N^1/4), so sometimes it is worth to factorize length to avoid unnecessary comparison of long strings.

这篇关于定期二进制字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！