Javascript字符串匹配模式帮助

Question

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

这是要求.

我有一个像这样的字符串,

这是下次您喜欢的石油和其他主题的快速指南

我需要将此字符串与这样的字符串匹配

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

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

我已经尝试了相交的Javascript脚本函数,对于某些字符串,它无法正常工作.

如何解决这个问题呢？这可以使用Regex完成吗？

请指教.

Answer 1

你必须找到最长的公共子串.

如果琴弦不长,我推荐使用Tim的方法.否则,这是具有动态编程的最长公共子串算法的Javascript实现.运行时为O(mn),其中m和n分别是2个字符串的长度.

示例用法:

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;
}