在Javascript中查找不包含/ indexOf / Regex的字符串中的子字符串

Question

我想知道子串是否在字符串中，而不使用Qazxswpoi，includes（任何类似的）或正则表达式的Javascript内置方法。基本上只是想学习一种算法方法。

这就是我到目前为止所拥有的

indexOf

我无法理解如何构建算法。一旦找到匹配的第一个字符，我就会转到下一个字符，如果匹配则继续到字符串的下一个索引？那么我是否需要一个与我目前正在进行的循环分开的递归函数？我正在努力改进算法思维。谢谢。

Answer 1

这是algorythm isSubstring的优化示例。它只迭代所需的最小字符数。

例如，如果字符串长度为20个字符且子字符串长度仅为5个字符，那么当我们到达字符串的第16个位置时，我们可以假设字符串中不存在子字符串（16 + 5 = 21> 20 ）

function isSubstring(string, substring){
    substringIndex = 0;

    // loop through string
    for(let i = 0; i< string.length; i++){

       //check the current substring index if it matches 
       if(string[i] === substring[substringIndex]){
           substringIndex++
          //continue searching... Would i then have to call another function recursively?
       }

    }

}

Answer 2

许多方法都是可能的。这是一个：创建一个更简单的函数，它将检查

function isSubstring(str, sub){
  if(sub.length > str.length) return false;
  for(let i = 0; i < str.length - sub.length + 1; i++){
    if(str[i] !== sub[0]) continue;
    let exists = true;
    for(let j = 1; j < sub.length && exists; j++){
        if(str[i+j] === sub[j]) continue;
        exists = false;
    }
    if(exists) return true;
  }
  return false;
}

//expected true
console.log(isSubstring("hello world", "hello"));
console.log(isSubstring("hello world", "world"));
console.log(isSubstring("hello world", "d"));
console.log(isSubstring("hello world", "o w"));
console.log(isSubstring("hello world", "rl"));
console.log(isSubstring("hello world", ""));

//expected false
console.log(isSubstring("hello world", "hello world 1"));
console.log(isSubstring("hello world", "helloo"));

字符串是否在具体指定位置，让我们在first字符串中将其命名为start。这很简单：你比较second和first[i]所有second[start+i]在0到i - 1的长度范围内。

然后第二步是对从0到第二个字符串长度的所有起始位置重复此函数，同时检查边界（在字符串结束后无法读取）。

稍后，当第一个版本可用时，您也可以进行一些优化。 :-)

Answer 3

在大海捞针的first上的每次迭代中，使用length从该索引中提取字符（索引加上针的长度）。如果切片的字符串与针匹配，则返回true：

slice

Answer 4

由于您表达了对递归方法的兴趣，因此需要考虑这一点。点击黄色降价部分可以看到剧透。

function isSubstring(string, substring) {
  for (let i = 0; i < string.length; i++) {
    const sliced = string.slice(i, i + substring.length);
    if (sliced === substring) {
      return true;
    }
  }
  return false;
}
console.log(isSubstring('foobar', 'oob'));
console.log(isSubstring('foobar', 'baz'));

function f(str, sub, i=0, j=0){
  if (j && j == sub.length)

return true;

if (i == str.length)

return false;

  if (str[i] == sub[j])
    return f(str, sub,

i+1, j+1);

return f(str, sub,

i+1, 0);

Answer 5

}

没有包含，没有.indexOf，没有RegExp。只是字符串。