如何检查字符串是否完全由相同的子字符串组成？ [英] How do I check if a string is entirely made of the same substring?

问题描述

我必须创建一个接受字符串的函数，它应根据是否返回 true 或 false 输入由重复的字符序列组成。给定字符串的长度始终大于 1 ，并且字符序列必须至少重复一次。

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)

我创建了以下函数：

function check(str){
  if(!(str.length && str.length - 1)) return false;
  let temp = '';
  for(let i = 0;i<=str.length/2;i++){
    temp += str[i]
    //console.log(str.replace(new RegExp(temp,"g"),''))
    if(!str.replace(new RegExp(temp,"g"),'')) return true;
  }
  return false;
}

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

检查这是真正问题的一部分。我买不起这样的无效解决方案。首先，它遍历字符串的一半。

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.

第二个问题是它正在使用 replace（）在每个循环中变慢。

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

推荐答案

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

There’s a nifty little theorem about strings like these.

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

A string consists of the same pattern repeated multiple times if and only if the string is a nontrivial rotation of itself.

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

Here, a rotation means deleting some number of characters from the front of the string and moving them to the back. For example, the string hello could be rotated to form any of these strings:

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

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

To see why this works, first, assume that a string consists of k repeated copies of a string w. Then deleting the first copy of the repeated pattern (w) from the front of the string and tacking it onto the back will give back the same string. The reverse direction is a bit trickier to prove, but the idea is that if you rotate a string and get back what you started with, you can apply that rotation repeatedly to tile the string with multiple copies of the same pattern (that pattern being the string you needed to move to the end to do the rotation).

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

Now the question is how to check whether this is the case. For that, there’s another beautiful theorem we can use:

如果x和y是相同长度的字符串，则x是

If x and y are strings of the same length, then x is a rotation of y if and only if x is a substring of yy.

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

As an example, we can see that lohel is a rotation of hello as follows:

hellohello
   ^^^^^

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

In our case, we know that every string x will always be a substring of xx (it’ll appear twice, once at each copy of x). So basically we just need to check if our string x is a substring of xx without allowing it to match at the first or halfway character. Here’s a one-liner for that:

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

假设 indexOf 为

希望这会有所帮助！

这篇关于如何检查字符串是否完全由相同的子字符串组成？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！