实现JavaScript的string.prototype.includes并分析其时间复杂度

Question

我想知道JavaScript中字符串方法

includes

的时间复杂度是多少，它决定了一个字符串是否可以在另一个字符串中找到。

例如

str1 = 'abcd'

substr = 'bcd'

,

console.log(str1.includes(substr))

将输出

true

我尝试实现我自己的包含内容，以更好地了解它的幕后工作原理。这是我的尝试。

function includes(str, substr) {
  let i = 0
  let j = 0
  let match = 0

  while(i < str.length) {
    if(str[i] === substr[j]) {
      match++
      i++
      j++
      if(match === substr.length) return true
    } else if(str[i] === substr[0]) {
      match = 0
      j = 0
    } else {
      match = 0
      j = 0
      i++
    }
  }

  return false
}

所以

console.log(includes('aaaabcd','aaaabc'))

将输出

true

。

在我看来，这里的时间复杂度是

nm

，其中

n

是

str

的长度，

m

是

substr

的长度。

我也想知道是否有人有更优雅的算法来实现它。也许使用滑动窗口方法？我不知道。

Answer 1

时间复杂度为 O(n)。我不认为情况会变得更好。但在你的实现中我做了一个小改变。

function includes(str, substr) {
  let i = 0
  let j = 0

  while(i < str.length) {
    if(str[i] === substr[j]) {
      i++
      j++
      if(j === substr.length) return true
    } else if(str[i] === substr[0]) {
      j = 0
    } else {
      j = 0
      i++
    }
  }

  return false
}