Справка шаблона сопоставления строк JavaScript
я должен найти немного слов или соответствия шаблону с помощью JavaScript.
это - требование.
у меня есть строка как это,
Вот краткое руководство по в следующий раз, когда Вы достигаете своей любимой нефти и некоторых других тем
и я должен соответствовать этой строке против строки как это
favorite oil and some other topics can be based on something blah blah
как я получаю пересечение блоков совпавшего текста?
Я уже попробовал, пересекают функцию сценария JavaScript, для некоторых строк, она не работает правильно.
Как решить эту проблему? это может быть сделано с помощью Regex?
Совет.
2 ответа
Вы должны найти Самую длинную общую подстроку .
Если строки не очень длинные, я рекомендую использовать подход Тима. В противном случае это реализация 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, поэтому метод пересечения доступен для всех строк.
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;
}
Также эта вспомогательная функция необходима для создания 2-мерного массива со всеми элементами, инициализированными до 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), но он прост и отлично работает для коротких строк:
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) );