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

Question

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

要匹配的样本字符串可以11223331122333.然而,10101不应该匹配.

来自python,我使用了RegEx

/(.+?)\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次.你也可以把它看作是由子力长度(子串的长度)12重复10次,子能力24次重复5次,子力量30次重复4次,或者是子能力60次重复2次(子力量由20的素数因子给出) (2*2*5)以不同的组合应用于6).现在,如果你检查你的字符串是否包含重复的60次sublength,并且检查失败,你也可以确定它不包含任何sublength,这是一个除数(即,素因子的组合)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.因此,暂时忘记有效的素数因子化不是一项简单的任务,我们可以将重复子串的检查限制为子长度/ 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上

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;
}