javascript - 检查两个字符串是否共享 JavaScript 中的公共(public)子字符串

Question

在 JavaScript 中是否有任何快速的方法来找出 2 个字符串是否包含相同的子字符串？例如我有这两个字符串:“audi is a car”和“audiA8”。

如您所见，单词“audi”在两个字符串中都有，但我们无法使用简单的 indexOf 或 RegExp 找到它，因为两个字符串中都有其他字符。

Answer 1

在生物信息学中做这类事情的标准工具是 BLAST程序。它用于比较两个分子片段(如 DNA 或蛋白质)以找出它们彼此对齐的位置 - 基本上是两个字符串(有时大小为数 GB)共享公共(public)子字符串的位置。

基本算法很简单，系统地将其中一个字符串分解成片段，然后将这些片段与另一个字符串进行比较。一个简单的实现是这样的:

// Note: not fully tested, there may be bugs:

function subCompare (needle, haystack, min_substring_length) {

    // Min substring length is optional, if not given or is 0 default to 1:
    min_substring_length = min_substring_length || 1;

    // Search possible substrings from largest to smallest:
    for (var i=needle.length; i>=min_substring_length; i--) {
        for (j=0; j <= (needle.length - i); j++) {
            var substring = needle.substr(j,i);
            var k = haystack.indexOf(substring);
            if (k != -1) {
                return {
                    found : 1,
                    substring : substring,
                    needleIndex : j,
                    haystackIndex : k
                }
            }
        }
    }
    return {
        found : 0
    }
}

您可以修改此算法以执行更多奇特的搜索，例如忽略大小写、模糊匹配子字符串、查找多个子字符串等。这只是基本思想。