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

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

"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()，这使得它变慢了。关于性能有更好的解决方案吗？

19069 次浏览
小开

你可以通过 捕捉组和 反向引用来做到这一点。只需检查它是第一个捕获值的重复。

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

在上述正则表达式内:

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

这里有正则表达式的解释

用于 RegExp 调试: https://regex101.com/r/pqlAuP/1/debugger

表现: https://jsperf.com/reegx-and-loop/13

小开

其中一个简单的想法是用“”的子字符串替换字符串，如果有任何文本存在，则为 false，否则为 true。

'ababababa'.replace(/ab/gi,'')
"a" // return false
'abababab'.replace(/ab/gi,'')
""// return true

小开

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

这个字符串的 Z- 函数是一个长度为 n 的数组，其中 i-th 元素等于从。开始的最大字符数 与 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 数组和提前退出

function z_function(s) {
var n = s.length;
var z = Array(n).fill(0);
var i, l, r;
//for our task we need only a half of z-array
for (i = 1, l = 0, r = 0; i <= n/2; ++i) {
if (i <= r)
z[i] = Math.min(r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];


//we can check condition and return here
if (z[i] + i === n && n % i === 0) return true;
    

if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return false;
//return z.some((zi, i) => (i + zi) === n && n % i === 0);
}
console.log(z_function("abacabacabac"));
console.log(z_function("abcab"));

然后需要检查除以 n 的索引 i。如果你发现这样的 i，那么字符串 s可以被压缩到 i的长度，你可以返回 true。

例如

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

Z-array 是

(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的子字符串，重复三次。

小开

我不熟悉 JavaScript，所以我不知道这会有多快，但这里有一个线性时间解决方案(假设合理的内置实现) ，只使用内置。我会用伪代码描述算法。

function check(str) {
t = str + str;
find all overlapping occurrences of str in t;
for each occurrence at position i
if (i > 0 && i < str.length && str.length % i == 0)
return true;  // str is a repetition of its first i characters
return false;
}

这个想法与 MBO 的回答类似。对于每个除长度的 i，str是其第一个 i字符的重复，当且仅当它在移位 i字符后保持不变。

我突然想到，这样一个内置的可能是不可用或效率低下。在这种情况下，始终可以手动实现 KMP 算法，这与 MBO 答案中的算法所需的代码量大致相同。

小开

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

递归函数 isrepeat (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

小开

假设字符串 S 的长度为 N，由子字符串 s 的副本构成，那么 s 的长度除以 N。例如，如果 S 的长度为15，那么子字符串的长度为1、3或5。

设 S 由 s 的(p * q)副本构成。然后 S 也是 p 的拷贝(s，重复 q 次)。因此我们有两种情况: 如果 N 是素数或1，那么 S 只能是长度为1的子串的副本。如果 N 是复合的，那么我们只需要检查长度为 N/p 的子串，对于质数 p 除以 S 的长度。

所以确定 N = S 的长度，然后找到它在时间 O (sqrt (N))中的所有素因子。如果只有一个因子 N，检查 S 是否是相同的字符串重复 N 次，否则对于每个质因子 p，检查 S 是否包含第一个 N/p 字符的 p 重复。

小开

我的方法类似于 gnasher729，因为它使用子字符串的潜在长度作为主要焦点，但是它没有那么多的数学和过程密集型:

原始字符串的长度

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

从 L/2到1的循环 S (整数部分)。如果 L/S 是一个整数，检查您的原始字符串与重复 L/S 次的原始字符串的第一个 S 字符的比较。

从 L/2向后循环而不是从1向前循环的原因是为了得到尽可能大的子字符串。如果您想要从1到 L/2的尽可能小的子字符串循环。示例: “ abababab”同时具有“ ab”和“ abab”作为可能的子字符串。如果您只关心 true/false 结果，那么两者中的哪一个会更快，这取决于将要应用该结果的字符串/子字符串的类型。

小开

我读了 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 页面。

小开
最佳答案

关于这样的弦有一个漂亮的小定理。

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

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

hello (the trivial rotation)
elloh
llohe
lohel
ohell

要了解为什么这样做，首先，假设一个字符串由字符串 w 的 k 个重复副本组成。然后从字符串的前面删除重复模式(w)的第一个副本并将其粘贴到后面将返回相同的字符串。相反的方向证明起来有点棘手，但是这个想法是，如果你旋转一个字符串并得到你开始时的结果，你可以重复地应用这个旋转来平铺同一个模式的多个副本(这个模式就是你需要移动到末尾来进行旋转的字符串)。

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

如果 x 和 y 是相同长度的字符串，那么 x 是 y 的旋转当且仅当 x 是广州欢聚时代的子字符串。

例如，我们可以看到 lohel是 hello的一个旋转，如下所示:

hellohello
^^^^^

在我们的例子中，我们知道每个字符串 x 将始终是 xx 的子字符串(它将出现两次，每次出现在 x 的副本中)。所以基本上我们只需要检查字符串 x 是否是 xx 的子字符串，而不允许它在第一个或中间字符处匹配。这里有一句俏皮话:

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

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

希望这个能帮上忙！

小开

这是用 Python 写的，我知道它不是平台，但它确实花了30分钟的时间。 附言 = > 巨蟒

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")
小开

下面的 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的和。

这个想法就是利用快速傅里叶变换来寻找频谱。 通过观察其他频率，人们应该也能够探测到这种奇怪的情况。

小开

这里的基本思想是检查任何潜在的子字符串，从长度1开始，到停止在原字符串长度的一半。我们只查看将原始字符串长度均匀分割的子字符串长度(即 str.length% substring.length = = 0)。

在移动到第二个字符之前，这个实现会查看每个可能的子字符串迭代的第一个字符，如果子字符串预期很长，这可能会节省时间。如果在检查完整的子字符串后没有发现不匹配，那么我们返回 true。

当用完要检查的潜在子字符串时，返回 false。

function check(str) {
const len = str.length;
for (let subl = 1; subl <= len/2; ++subl) {
if ((len % subl != 0) || str[0] != str[subl])
continue;
    

let i = 1;
for (; i < subl; ++i)
{
let j = 0;
for (; j < len; j += subl)
if (str[i] != str[j + i])
break;
if (j != len)
break;
}
    

if (i == subl)
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

小开

这个问题已经发布一年多了，但是我使用字符串长度和对象形式来验证它是真还是假。

const check = (str) => {
let count = 0;
let obj = {};
if (str.length < 2) return false;
  

for(let i = 0; i < str.length; i++) {
if (!obj[str[i]]) {
count+=1;
obj[str[i]] = 0;
};
obj[str[i]] = obj[str[i]] + 1;
};
  

if (Object.values(obj).every(item => item === 1)) {
return false
};
  

if ([...str].length%count === 0) {
return true
} else {
return false
};
};


console.log(check("abcabcabcac")) // false
console.log(check("aaa")) // true
console.log(check("acaca")) // false
console.log(check("aa")) // true
console.log(check("abc")) // false
console.log(check("aabc")) // false


提交答案