JavaScript字符串匹配模式帮助

Question

我需要使用Javascript查找几个单词或匹配模式。

这是要求：

我有一个字符串，像这样：

这里是下一次你拿出你最喜欢的油和其他主题的快速指南

我需要将此字符串与像这样的字符串进行匹配：

favorite oil and some other topics can be based on something blah blah

如何获取匹配文本块的交集？

我已经尝试使用JavaScript的intersect函数，但对于某些字符串，它无法正常工作。

如何解决这个问题？可以使用正则表达式吗？

请给出建议。

- kakopappa

Answer 1

你需要找到最长公共子串。

如果字符串不是很长，我建议使用Tim的方法。否则，这是一个使用动态规划算法实现的最长公共子串Javascript代码。运行时间为O(mn)，其中m和n分别是两个字符串的长度。

一个使用示例：

var first = "Here is a quick guide for the next time you reach for your favorite oil and some other topics";
var second = "favorite oil and some other topics can be based on something blah blah";

console.log(first.intersection(second)); // ["favorite oil and some other topic"]

这是算法实现。它返回最长公共子串的数组。扩展了本地String类，因此intersect方法在所有字符串上都可用。

String.prototype.intersection = function(anotherString) {
    var grid = createGrid(this.length, anotherString.length);
    var longestSoFar = 0;
    var matches = [];

    for(var i = 0; i < this.length; i++) {
        for(var j = 0; j < anotherString.length; j++) {
            if(this.charAt(i) == anotherString.charAt(j)) {
                if(i == 0 || j == 0) {
                    grid[i][j] = 1;
                }
                else {
                    grid[i][j] = grid[i-1][j-1] + 1;
                }
                if(grid[i][j] > longestSoFar) {
                    longestSoFar = grid[i][j];
                    matches = [];
                }
                if(grid[i][j] == longestSoFar) {
                    var match = this.substring(i - longestSoFar + 1, i);
                    matches.push(match);
                }
            }
        }
    }
    return matches;
}

还需要这个辅助函数来创建一个所有元素均初始化为0的二维数组。

// create a 2d array
function createGrid(rows, columns) {
    var grid = new Array(rows);
    for(var i = 0; i < rows; i++) {
        grid[i] = new Array(columns);
        for(var j = 0; j < columns; j++) {
            grid[i][j] = 0;
        }
    }
    return grid;
}

- Anurag

---

好的回答。我曾考虑自己实现这个功能，但还有其他工作要做。 - Tim Down

@Aruna - 很高兴它对你有用。 @Tim - 它很快但缺乏简洁性。还有另一个使用后缀树的算法，时间复杂度为O(n+m)，但今天不讨论 :) - Anurag

Answer 2

这种方法并不是很高效，通常有更好的方法来处理这个问题（请参见@Anurag的答案），但对于短字符串来说，它是简单且有效的：

function stringIntersection(str1, str2) {
    var strTemp;

    // Swap parameters if necessary to ensure str1 is the shorter
    if (str1.length > str2.length) {
        strTemp = str1;
        str1 = str2;
        str2 = strTemp;
    }

    // Start with the whole of str1 and try shorter substrings until
    // we have a common one
    var str1Len = str1.length, l = str1Len, start, substring;
    while (l > 0) {
        start = str1Len - l;
        while (start >= 0) {
            substring = str1.slice(start, l);
            if (str2.indexOf(substring) > -1) {
                return substring;
            }
            start--;
        }
        l--;
    }
    return "";
}

var s1 = "Here is a quick guide for the next time you reach"
       + " for your favorite oil and some other topics";
var s2 = "favorite oil and some other topics can be based on"
       + " something blah blah";

alert( stringIntersection(s1, s2) );

- Tim Down

Answer 3

一个简单的字符串过滤器的 polyfill

if (!String.prototype.intersection) {
  String.prototype.intersection = function(anotherString, caseInsensitive = false) {
    const value = (caseInsensitive) ? this.toLowerCase()          : this;
    const comp  = (caseInsensitive) ? anotherString.toLowerCase() : anotherString;
    const ruleArray = comp.split("").reduce((m,v) => {m[v]=true; return m;} ,{})
    return this.split("").filter( (c, i) => ruleArray[value[i]] ).join("")
  }
}

"HelloWorld".intersection("HEWOLRLLODo", true)

"HelloWorld" - 不区分大小写

"HelloWorld".intersection("HEWOLRLLODo")

"HoWo" - 区分大小写

- Brian