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




string algorithm (8)

也许最快的算法方法是在线性时间内构建 Z-function

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

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

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-array并提前退出

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+z[i]=n 那么字符串 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的子串重复三次。

我必须创建一个接受字符串的函数,它应该根据输入是否包含重复的字符序列返回 truefalse 。 给定字符串的长度始终大于 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() ,这使得它变慢。 有关性能的更好解决方案吗?


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

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

此代码查找“全长”贡献,在重复字符串中必须为零,但字符串 accbbd 也被视为重复,因为它是两个重复字符串 ababab012012

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


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

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

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

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

为了解其原因,首先,假设一个字符串由k个字符串w的重复副本组成。 然后从字符串的前面删除重复图案(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;
}

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

希望这可以帮助!


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

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


我不熟悉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的答案。 对于每个除以长度的 istr 是其前 i 字符的重复,当且仅当它在移动 i 字符后保持不变时才重复。

我想到这样的内置可能不可用或效率低下。 在这种情况下,总是可以手动实现 KMP算法 ,这需要与MBo的答案中的算法大致相同的代码量。


我的方法类似于gnasher729,因为它使用子串的潜在长度作为主要焦点,但它的数学和过程密集程度较低:

L:原始字符串的长度

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

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

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


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


用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")




algorithm