我需要使用
Javascript找到几个单词或匹配模式.
这是要求.
我有一个像这样的字符串,
Here is a quick guide for the next
time you reach for your favorite oil and some other topics
我需要将此字符串与这样的字符串匹配
favorite oil and some other topics can be based on something blah blah
我如何获得匹配的文本块的交集？
我已经尝试了相交的Javascript脚本函数,对于某些字符串,它无法正常工作.
如何解决这个问题呢？这可以使用Regex完成吗？
请指教.
解决方法
你必须找到
Longest common substring.
如果琴弦不长,我推荐使用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;
}
