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

我正在寻找一种方法来检查字符串是否是周期性的或不使用 JavaScript。

要匹配的示例字符串可以是11223331122333。然而，10101不应该匹配。

来自 python，我使用了 RegEx

/(.+?)\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;
}

不幸的是，没有用于与另一个字符串的子字符串进行比较的 String 方法in place（例如，在 C 语言中，这将是strncmp(str1, str2 + offset, length)).

假设您的字符串长度为 120，并且由长度为 6 的子字符串重复 20 次组成。您也可以将其视为由子长度（子字符串的长度）12 重复 10 次、子长度 24 重复 5 次、子长度 30 重复 4 次或子长度 60 重复 2 次组成（子长度由 20 的质因数给出） (2*2*5)应用于6)的不同组合。现在，如果您检查字符串是否包含 60 的子长度重复 2 次，并且检查失败，您还可以确定它不会包含任何 60 的除数（即质因数的组合）的子长度，包括6个。也就是说，上面代码所做的很多检查都是多余的。例如，在长度为 120 的情况下，上述代码检查（幸运的是大多数时候很快就会失败）以下子长度：1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30、40、60（按顺序：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。因此，暂时忘记有效的质因数分解并不是一项简单的任务，我们可以将重复子串的检查限制为子长度 length/p 的 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 上，它比第一个版本快得多，但在 Chromium 上，它速度较慢，只有在长度为数千的字符串时才会变得更快。最后发现问题出在数组上distinct_primes()创建并传递给is_periodic()。解决方案是通过合并这两个函数来摆脱数组。代码如下，测试结果在上http://jsperf.com/periodic-strings-1/5 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 http://jsperf.org/是绝对的，并且不同的实验者使用不同的机器将有助于不同的通道组合。如果您想可靠地比较两个 JavaScript 引擎，您需要编辑实验的新私有版本。