使用动态空格比较两个字符串的最快方法是什么？

Question

我有两个字符串bigstring和smallstring，每个字符串都是一个由单词组成的段落。然而，在每个单词中间，随机长度的空格字符(\s正则表达式)。

例如，bigstring可能是像hello world这样的。 smallstring也是如此。

我想要做的是，检查smallstring在bigstring 中是否为子字符串(逐字)，其中它们之间的\s+部分被视为相同，并且不区分大小写。例如，如果 bigstring = "hello \t\r\n world \n foobar" smallstring = "HELLO \t world" 那么smallstring是bigstring的子字符串。 bigstring = "hello \t\r\n world \n foobar" smallstring = "HEL" 这不是子字符串(逐字)，因为在bigstring中没有一个名为hel的词。 bigstring = "the \t\r\n nest" smallstring = "then \n est" 这也不是(逐字)子字符串。

一种方法是将两个字符串标记化为数组，即将\s+之间的内容分解为标记，而\s+是分隔符。然后逐字检查一个数组是否以不区分大小写的方式按顺序和连续地包含在另一个数组中。

但在这种情况下，我需要速度优先，因为它应该是最快的方法。

有人知道如何检查这个吗？

我也许正在考虑一种方法，通过循环遍历这两个字符串，逐个字符地检查它们，但不确定如何实现。

谢谢

- omega

---

你可以尝试的一个选项是，通过将 smallstring 按照 /\s+/ 分割并转义每个组件，然后使用 "\\s+" 将其重新连接起来，动态地创建一个正则表达式，并在 bigstring 上运行该正则表达式。 - Ry-

可能有一些更智能的算法，但简单的算法是创建一个StringBuilder实例来逐个字符地构建（每个字符串一个），在for循环中使用状态变量将任何一系列空格转换为一个空格，然后最后你可以只做一个正常的子字符串。所以基本上用一个单一的空格替换所有空格是唯一困难的部分。 - user2080225

你可以使用 replace(/\s/+, " ") 的方式，但我感觉如果你在一个循环中完成所有操作会更快。 - omega

如果smallstring是用户输入，最快的方法可能是在搜索之前使用bigstring中的单词或字符生成查找对象/映射表。 - Slai

执行时间与内存分配密切相关，因此我认为最快的方法应该是indexOf和for循环的某种组合。RegExp是最短代码的方式，但在大多数情况下绝对不是最快的。 - bigless

Answer 1

我不确定这个速度排名在哪里，但是这是否达到了你的目标（现在已经编辑以解决“impl”与“mpl”的边缘情况，通过添加前导空格）

var isSubstring = function(bigstring, smallstring) {
  bigstring = " " + bigstring.replace(/\s+/g, " ").toLowerCase() + " "
  smallstring = " " + smallstring.replace(/\s+/g, " ").toLowerCase() + " "
  return(bigstring.indexOf(smallstring) >= 0)
}

添加一个结尾空格（现在也可以是开头空格）可以涵盖 smallstring 是单个词片段的情况（例如，在您上面的示例和下面的评论中，'hel' 与 'hello' 以及 'impl' 与 'mpl'）

使用案例：

bigstring = "hello   \t\r\n  world \n foobar"
smallstring = "HELLO \t world"
console.log(isSubstring(bigstring, smallstring))
//evaluates to true

bigstring = "hello   \t\r\n  world \n foobar"
smallstring = "HEL"
console.log(isSubstring(bigstring, smallstring))
// evaluates to false

bigstring = "impl"
smallstring = "mpl"
console.log(isSubstring(bigstring, smallstring))
// evaluates to false

- Eric

---

@ClayFerguson 正则表达式是上帝送给地球的美丽小谜题，为我们枯燥乏味的生活带来了欢乐和简洁。但好吧。 - Eric

这似乎可以工作，但是循环了太多完整的字符串。我认为我正在寻找一个更优化的版本，最多只循环两个字符串，并在那个1个循环中执行所有需要检查的操作。 - omega

因为这些字符串可能非常非常大。 - omega

@Omega，正则表达式不应该进行不必要的循环。坦白说，如果没有错别字，Eric的解决方案绝对应该被接受。它是正确的，并且是最佳方法（除非有错别字）。我对正则表达式不够熟悉，但我知道他发布的方法是最好的。然而，当你有一个足够大的字符串时，会有某个拐点，此时通过构建两个新的字符串到StringBuilder中（将空格转换为一个空格）会更好，但我不知道什么规模的字符串足够大以至于使正则表达式的性能下降。 - user2080225

@ClayFerguson：你知道这是最好的方式，因为...？ - Ry-

Answer 2

正则表达式绝对不是最快的，但你可以使用从小字符串生成的RegExp搜索大字符串:

bigstring = "hello   \t\r\n  world \n foobar"

smallstring = "HELLO \t world"

r = new RegExp( '\\b' + smallstring.replace(/\s+/g, '\\s+') + '\\b', 'i' )

console.log( r.test(bigstring), r ) // true /\bHELLO\s+world\b/i

一个更快的不区分大小写的字符串搜索很可能会使用charCodeAt和/或某种单词/标记查找结构，例如https://github.com/bvaughn/js-search所使用的。

- Slai

Answer 3

F(a)函数将返回字符串a的统一版本。所谓统一版本是指所有连续的空格字符将被替换为单个空格，并且所有字母都将转换为小写。该函数可以在线性时间内计算 - O(|a|)。

在这种情况下，您需要检查F(smallstring)是否是F(bigstring)的子字符串。为了快速处理这个问题，您可以使用一些标准算法，如KMP。

- Sereja Nagin