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

Question

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

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

不幸的是，没有一个字符串方法可以与另一个字符串的子字符串进行比较（例如，在C语言中，strncmp(str1,str2+offset,length）)。

假设您的字符串长度为120，由长度为6的子字符串组成，重复20次。您也可以将其看作由重复10次的子串长度12、重复5次的子串长度24、重复4次的子串长度30或重复2次的子串长度60组成（子串由不同组合中应用的质因数20(2*2*5)到6给出）。现在，如果您检查字符串是否包含重复2次的60的子长度，并且检查失败，那么您还可以确保它不会包含任何60的除数（即素因子的组合）的子长度，包括6。换句话说，上面代码所做的许多检查都是多余的。例如，在长度为120的情况下，上面的代码检查（幸运的是大多数时间都很快失败）以下子级:1、2、3、4、5、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。因此，暂时忘记有效的素数因式分解并不是一项简单的任务，我们可以将重复子串的检查限制在子串长度/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_periode()的数组有关。解决方案是通过合并这两个函数来摆脱数组。代码如下所示，html" target="_blank">测试结果在http://jsperf.com/periody-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引擎，您需要编辑实验的一个新的私有版本。