Javascript string matching pattern help

Question

Мне нужно найти несколько слов или соответствующий шаблон, используя Javascript.

это требование.

У меня есть строка, как это,

Вот краткое руководство для следующего времени вы достигнете для вашего любимого масла и некоторых другие тема

и мне нужно, чтобы соответствовать этой строке против такой строки

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

Как получить пересечение соответствующих текстовых блоков?

Я уже пробовал пересекать функцию скрипта Javascript, для некоторых строк он работает неправильно.

Как решить эту проблему? можно ли это сделать с помощью Regex?

Прошу совета.

Answer 1

Вы должны найти Longest common substring.

Если строки не очень длинны, я рекомендую использовать подход Тима. В противном случае это реализация 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; 
} 

необходим также эта вспомогательная функция для создания 2d массива со всеми элементами инициализации 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; 
} 

Answer 2

Это не очень эффективно, и есть намного лучшие способы сделать это в целом (см @ ответ Анурага), но это просто и прекрасно работает для коротких строк:

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

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", правда)

"HelloWorld" - регистронезависимы

"HelloWorld" .intersection ("HEWOLRLLODo")

"Howo" - случай чувствительный