使用字符串函数查找定期字符串

Question

我正在寻找一种方法来检查字符串是否定期使用JavaScript。

匹配的样本字符串可以是11223331122333。而不应该匹配。

从巨蟒的到来，我用正则表达式

/(.+?)\1+$/ 

但它是相当缓慢。有没有任何字符串方法可以做到这一点？

Answer 1

下面的代码的想法是考虑所有长度的子串，原始字符串可以分成均匀的，并检查它们是否重复跨越原始字符串。一个简单的方法是检查长度从1到长度的平方根的所有除数。如果分部产生一个整数，则它们是除数，这也是一个补充除数。例如，对于长度为100的字符串，除数为1,2,4,5,10，并且互补除数为100（因为子字符串将仅出现一次，所以不用作子字符串长度），50,25,20（和10 ，我们已经找到了）。

function substr_repeats(str, sublen, subcount) 
{ 
    for (var c = 0; c < sublen; c++) { 
     var chr = str.charAt(c); 
     for (var s = 1; s < subcount; s++) { 
     if (chr != str.charAt(sublen * s + c)) { 
      return false; 
     } 
     } 
    } 
    return true; 
} 

function is_periodic(str) 
{ 
    var len = str.length; 
    if (len < 2) { 
     return false; 
    } 
    if (substr_repeats(str, 1, len)) { 
     return true; 
    } 
    var sqrt_len = Math.sqrt(len); 
    for (var n = 2; n <= sqrt_len; n++) { // n: candidate divisor 
     var m = len/n; // m: candidate complementary divisor 
     if (Math.floor(m) == m) { 
     if (substr_repeats(str, m, n) || n != m && substr_repeats(str, n, m)) { 
      return true; 
     } 
     } 
    } 
    return false; 
} 

不幸的是，对于在适当位置比较另一个字符串的子串（例如，在那将是strncmp(str1, str2 + offset, length) C语言）没有字符串方法。

---

假设您的字符串长度为120，并且由长度为6的子字符串重复20次组成。你可以把它看作是由一个重复次数为10的次长（重复长度）12，重复5次的重复次数24，重复次数为4的重复次数30或重复次数为60的重复长度60组成（重复次数由20 （2 * 2 * 5）以不同组合应用于6）。现在，如果你检查你的字符串是否包含60的重复长度重复2次，并且检查失败，那么你也可以确定它不包含作为除数（即主要因素的组合）为60的任何长度，其中包括6.换句话说，上述代码所做的很多检查都是多余的。例如，在长度为120的情况下，上述代码检查（幸运的是，大部分时间很快失败）下列超长：1,2,3,4,5,6,8,10,12,15,20,24， （按此顺序：1,60,2,40,3,30,4,24,5,20,6,15，8,12,10）中的一个或多个。其中，只有以下是必要的：24,40,60。它们是2 * 2 * 2 * 3,2 * 2 * 2 * 5,2 * 2 * 3 * 5，即质数的组合120（ 2 * 2 * 2 * 3 * 5），每个（非重复）素数中的一个被取出，或者，如果您愿意，可以是120/5,120/3,120/2。因此，暂时忘记有效的素因子分解不是一项简单的任务，我们可以将重复子串的检查限制为子长度为p的子串，其中p是长度的主要因子。以下是最简单平凡的实现：

function substr_repeats(str, sublen, subcount) { see above } 

function distinct_primes(n) 
{ 
    var primes = n % 2 ? [] : [2]; 
    while (n % 2 == 0) { 
     n /= 2; 
    } 
    for (var p = 3; p * p <= n; p += 2) { 
     if (n % p == 0) { 
     primes.push(p); 
     n /= p; 
     while (n % p == 0) { 
      n /= p; 
     } 
     } 
    } 
    if (n > 1) { 
     primes.push(n); 
    } 
    return primes; 
} 

function is_periodic(str) 
{ 
    var len = str.length; 
    var primes = distinct_primes(len); 
    for (var i = primes.length - 1; i >= 0; i--) { 
     var sublen = len/primes[i]; 
     if (substr_repeats(str, sublen, len/sublen)) { 
     return true; 
     } 
    } 
    return false; 
} 

---

试图从我的Linux PC上这个代码，我有一个惊喜：在Firefox它比第一个版本快得多，但铬是慢，成为仅适用于长度为数千的字符串。最后我发现问题与distinct_primes()创建并传递到is_periodic()的数组有关。解决方案是通过合并这两个函数来摆脱数组。该代码是下面和测试结果上http://jsperf.com/periodic-strings-1/5

function substr_repeats(str, sublen, subcount) { see at top } 

function is_periodic(str) 
{ 
    var len = str.length; 
    var n = len; 
    if (n % 2 == 0) { 
     n /= 2; 
     if (substr_repeats(str, n, 2)) { 
     return true; 
     } 
     while (n % 2 == 0) { 
     n /= 2; 
     } 
    } 
    for (var p = 3; p * p <= n; p += 2) { 
     if (n % p == 0) { 
     if (substr_repeats(str, len/p, p)) { 
      return true; 
     } 
     n /= p; 
     while (n % p == 0) { 
      n /= p; 
     } 
     } 
    } 
    if (n > 1) { 
     if (substr_repeats(str, len/n, n)) { 
     return true; 
     } 
    } 
    return false; 
} 

请记住，通过jsperf.org收集的定时是绝对的，并且与不同的机器，不同的实验者将有助于信道的不同组合。如果你想可靠地比较两个JavaScript引擎，你需要编辑一个新的私有版本的实验。

Answer 2

一种选择是继续使用正则表达式，而是使之贪婪通过降低?：

/^(.+)\1+$/ 

取决于精确的输入字符串，它可能会降低回溯所需的量，加快配套。

Answer 3

如果字符串是周期性：

• 的最后一个元素将是周期的最后一个元素以及
• 周期长度将划分字符串长度

所以我们可以一个超级贪婪的算法，取最后一个元素并检查出现直到长度的一半。当我们找到一个时，我们检查子字符串的长度是否与主字符串长度相除，然后才检测字符串。

function periodic(str){ 
    for(var i=0; i<=str.length/2; i++){ 
     if(str[i] === str[str.length-1] && str.length%(i+1) === 0){ 
      if (str.substr(0,i+1).repeat(str.length/(i+1)) === str){ 
     return true; 
      } 
     } 
    } 
    return false; 
} 

Answer 4

直接的办法是划分字符串转换成相等大小的块，并测试 每个夹头是否是相同的第一个块。这里有一个算法 ，通过将块大小从1增加到length/2，跳过块大小为 ，这些块不会干净地划分长度。

function StringUnderTest (str) { 
    this.str = str; 
    this.halfLength = str.length/2; 
    this.period = 0; 
    this.divideIntoLargerChunksUntilPeriodicityDecided = function() { 
     this.period += 1; 
     if (this.period > this.halfLength) 
      return false; 
     if (this.str.length % this.period === 0) 
      if (this.currentPeriodOk()) 
       return true; 
     return this.divideIntoLargerChunksUntilPeriodicityDecided(); 
    }; 
    this.currentPeriodOk = function() { 
     var patternIx; 
     var chunkIx; 
     for (chunkIx=this.period; chunkIx<this.str.length; chunkIx+=this.period) 
      for (patternIx=0; patternIx<this.period; ++patternIx) 
       if (this.str.charAt(patternIx) != this.str.charAt(chunkIx+patternIx)) 
        return false; 
     return true; 
    }; 
} 

function isPeriodic (str) { 
    var s = new StringUnderTest(str); 
    return s.divideIntoLargerChunksUntilPeriodicityDecided(); 
} 

我没有测试过的速度，虽然...

Answer 5

还有值得一提的其纯粹的美一个答案。它不是我的，我只是从Python版本，这是在这里将它改编：How can I tell if a string repeats itself in Python?

function is_periodic(s) 
{ 
    return (s + s.substring(0, s.length >> 1)).indexOf(s, 1) > 0; 
} 

不幸的是，速度不看齐的美丽（以及美遭受了位在适应从Python，因为indexOf()有一个开始参数，但不是停止参数）。与正则表达式解决方案的比较以及我的其他答案的功能是here。即使以[4，400]中的一个随机长度为基础的字符串，我的其他答案的功能表现也会更好。不过，该解决方案比正则表达式解决方案更快。

该解决方案可能被称为“相移解决方案”。该字符串被视为一个波形，它在移动其相位时与自身相同。

该解决方案在我的其他答案的那些的优点是，它可以很容易地适应返回最短重复子，像这样：

function repeating_substr(s) 
{ 
    period = (s + s.substring(0, s.length >> 1)).indexOf(s, 1); 
    return period > 0 ? s.substr(0, period) : null; 
}