如何检查字符串是否完全由相同的子字符串组成？

javascript string algorithm

2022-08-30 04:30:45

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

"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

检查这是真正问题的一部分。我负担不起像这样的非高效解决方案。首先，它循环穿过字符串的一半。

第二个问题是它在每个循环中使用，这使得它很慢。在性能方面是否有更好的解决方案？replace()

答案 1

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

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

在这里，旋转意味着从字符串的前面删除一些字符，然后将它们移动到后面。例如，可以旋转字符串以形成以下任何字符串：hello

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell

要了解为什么这样做有效，首先，假设字符串由字符串 w 的 k 个重复副本组成。然后从字符串的前面删除重复模式（w）的第一个副本并将其固定到后面将返回相同的字符串。相反的方向有点难以证明，但这个想法是，如果你旋转一个字符串并取回你开始时的内容，你可以重复地应用该旋转来平铺具有相同模式的多个副本的字符串（该模式是你需要移动到末尾进行旋转的字符串）。

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

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

作为一个例子，我们可以看到，这是如下的旋转：lohelhello

hellohello
   ^^^^^

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

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

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

希望这有帮助！

答案 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

在上面的正则表达式中：