How do I check if a string is entirely made of the same substring?

Question

I have to create a function which takes a string, and it should return true or false based on whether the input consists of a repeated character sequence. The length of the given string is always greater than 1 and the character sequence must have at least one repetition.

"aa" // true(entirely contains two strings "a")
"aaa" //true(entirely contains three string "a")
"abcabcabc" //true(entirely containas three strings "abc")

"aba" //false(At least there should be two same substrings and nothing more)
"ababa" //false("ab" exists twice but "a" is extra so false)

I have created the below function:

"aa" // true(entirely contains two strings "a")
"aaa" //true(entirely contains three string "a")
"abcabcabc" //true(entirely containas three strings "abc")

"aba" //false(At least there should be two same substrings and nothing more)
"ababa" //false("ab" exists twice but "a" is extra so false)

Checking of this is part of the real problem. I can't afford a non-efficient solution like this. First of all, it's looping through half of the string.

The second problem is that it is using replace() in each loop which makes it slow. Is there a better solution regarding performance?

Answer 1

关于这样的字符串，有一个漂亮的小定理。

当且仅当字符串本身是非平凡的旋转时，字符串才由重复多次的相同模式组成。

在这里，旋转表示从字符串的开头删除一些字符并将其移到后面。例如，hello可以旋转字符串以形成以下任何字符串：

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

要了解其工作原理，首先，假设一个字符串包含k个字符串w的k个重复副本。然后从字符串的开头删除重复图案（w）的第一个副本，然后将其粘贴到背面，将得到相同的字符串。相反的方向很难证明，但是其想法是，如果旋转字符串并返回开始的位置，则可以重复应用该旋转，以用相同模式的多个副本平铺字符串（该模式是您需要移至末尾进行旋转的字符串）。

现在的问题是如何检查是否是这种情况。为此，我们可以使用另一个美丽的定理：

如果x和y是相同长度的字符串，则当且仅当x是yy的子字符串时，x是y的旋转。

作为示例，我们可以看到这lohel是hello如下的轮换：

hellohello
   ^^^^^

在我们的例子中，我们知道每个字符串x始终是xx的子字符串（它将出现两次，在x的每个副本处出现一次）。因此，基本上，我们只需要检查字符串x是否是xx的子字符串，而不允许它与第一个字符或中途字符匹配。这是一线的：

function check(str) {
    return (str + str).indexOf(str, 1) !== str.length;
}

假设indexOf使用快速字符串匹配算法实现，它将在时间O（n）中运行，其中n是输入字符串的长度。

希望这可以帮助！

Answer 2

您可以通过捕获组和反向引用来实现。只需检查它是第一个捕获值的重复即可。

function check(str) {
  return /^(.+)\1+$/.test(str)
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

在上面的RegExp中：

1. ^并$代表开始和结束锚预测的位置。
2. (.+)捕获任何模式并捕获值（除外\n）。
3. \1是第一个捕获值的后向引用，\1+将检查捕获值的重复。

正则表达式的解释在这里

对于RegExp调试，请使用：https : //regex101.com/r/pqlAuP/1/debugger

性能：https : //jsperf.com/reegx-and-loop/13

Answer 3

最快的算法方法也许是在线性时间内建立Z函数：

此字符串的Z函数是一个长度为n的数组，其中第i个元素等于从与s的第一个字符重合的位置i开始的最大字符数。

换句话说，z [i]是s和s的后缀（从i开始）之间最长的公共前缀的长度。

C ++实现供参考：

vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

JavaScript实现
添加了优化-构建一半的z数组并提前退出

vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

然后，您需要检查i除以n的索引。如果找到这样的字符串i，i+z[i]=n则s可以将其压缩为长度，i然后可以返回true。

例如，对于

string s= 'abacabacabac'  with length n=12`

Z数组是

(0, 0, 1, 0, 8, 0, 1, 0, 4, 0, 1, 0)

我们可以找到

i=4
i+z[i] = 4 + 8 = 12 = n
and
n % i = 12 % 4 = 0`

因此s可以表示为长度为4的子字符串重复三遍。

Answer 4

我阅读了gnasher729的答案并实现了它。这个想法是，如果有任何重复，那么就必须（也）有素数个重复。

function* primeFactors (n) {
    for (var k = 2; k*k <= n; k++) {
        if (n % k == 0) {
            yield k
            do {n /= k} while (n % k == 0)
        }
    }
    if (n > 1) yield n
}

function check (str) {
    var n = str.length
    primeloop:
    for (var p of primeFactors(n)) {
        var l = n/p
        var s = str.substring(0, l)
        for (var j=1; j<p; j++) {
            if (s != str.substring(l*j, l*(j+1))) continue primeloop
        }
        return true
    }
    return false
}

稍微不同的算法是这样的：

function check (str) {
    var n = str.length
    for (var p of primeFactors(n)) {
        var l = n/p
        if (str.substring(0, n-l) == str.substring(l)) return true
    }
    return false
}

我已经更新了jsPerf页面，其中包含该页面上使用的算法。

Answer 5

假定字符串S的长度为N，并且由子字符串s的重复项组成，则s的长度除以N。例如，如果S的长度为15，则子字符串的长度为1、3或5。

令S由的（p * q）个副本组成。然后，S也由p份（s，重复q次）组成。因此，我们有两种情况：如果N为素数或1，则S只能由长度为1的子串的副本组成。如果N为复合的，则我们仅需检查长度为N / p的子串s以进行素数p除法S的长度。

因此，确定N = S的长度，然后在时间O（sqrt（N））中找到其所有主要因子。如果只有一个因子N，请检查S是否是同一字符串重复N次，否则，对于每个素数p，请检查S是否由前N / p个字符的p个重复组成。

Answer 6

我认为递归函数也可能非常快。第一个观察结果是最大重复图案长度是整个字符串的一半。我们可以测试所有可能的重复图案长度：1、2、3，...，str.length / 2

递归函数isRepeating（p，str）测试是否在str中重复此模式。

如果str大于模式，则递归要求第一部分（与p相同的长度）为重复部分，其余部分为str。因此，str有效地分解为长度为p.length的片段。

如果测试的模式和str大小相等，则递归将成功结束。

如果长度不同（出现“ aba”和模式“ ab”的情况）或块数不同，则返回false，从而扩展递归。

function check(str)
{
  if( str.length==1 ) return true; // trivial case
  for( var i=1;i<=str.length/2;i++ ) { // biggest possible repeated pattern has length/2 characters

    if( str.length%i!=0 ) continue; // pattern of size i doesn't fit
    
    var p = str.substring(0, i);
    if( isRepeating(p,str) ) return true;
  }
  return false;
}


function isRepeating(p, str)
{
  if( str.length>p.length ) { // maybe more than 2 occurences

    var left = str.substring(0,p.length);
    var right = str.substring(p.length, str.length);
    return left===p && isRepeating(p,right);
  }
  return str===p; 
}

console.log(check('aa')) //true
console.log(check('aaa')) //true 
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

性能：https : //jsperf.com/reegx-and-loop/13

Answer 7

用Python编写。我知道这不是平台，但是确实花了30分钟的时间。PS => PYTHON

def checkString(string):
    gap = 1 
    index= 0
    while index < len(string)/2:
        value  = [string[i:i+gap] for i in range(0,len(string),gap) ]

        x = [string[:gap]==eachVal for eachVal in value]

        if all(x):
            print("THEY ARE  EQUAL")
            break 

        gap = gap+1
        index= index+1 

checkString("aaeaaeaaeaae")

Answer 8

我的方法与gnasher729类似，因为它使用子字符串的潜在长度作为主要焦点，但是它的数学运算量和处理强度较低：

L：原始字符串的长度

S：有效子字符串的潜在长度

将S从L / 2的整数部分循环到1。如果L / S是整数，则将原始字符串与重复L / S次的原始字符串的第一个S个字符进行比较。

从L / 2向后而不是从1开始循环的原因是要获得最大的子字符串。如果要最小的子串循环，从1到L / 2。示例：“ abababab”具有“ ab”和“ abab”作为可能的子字符串。如果仅关心真/假结果，则两者中哪一个会更快，这取决于将应用于的字符串/子字符串的类型。

Answer 9

以下Mathematica代码几乎可以检测到该列表是否至少重复了一次。如果字符串重复至少一次，则返回true，但是如果字符串是重复字符串的线性组合，则也可能返回true。

IsRepeatedQ[list_] := Module[{n = Length@list},
   Round@N@Sum[list[[i]] Exp[2 Pi I i/n], {i, n}] == 0
];

该代码查找“全长”部分，在重复的字符串中该部分必须为零，但是该字符串accbbd也被视为重复的，因为它是两个重复的字符串ababab和的总和012012。

这个想法是使用快速傅立叶变换，并寻找频谱。通过查看其他频率，人们也应该能够检测到这种奇怪的情况。