Javascript string matching pattern help

Question

i need to find few words or matching pattern using a Javascript.

this is the requirement.

i have a string like this,

Here is a quick guide for the next time you reach for your favorite oil and some other topics

and i need to match this string against a string like this

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

how do i get the intersection of matching text blocks?

I already tried intersect Javascript script function, for some strings it's not working properly.

How to solve this problem? can this be done using Regex?

Please advice.

Anurag · Accepted Answer · 2010-02-12 11:19:47Z

8

You have to find the Longest common substring.

If the strings are not very long, I recommend using Tim's approach. Otherwise, this is a Javascript implementation of the Longest common substring algorithm with dynamic programming. The runtime is O(mn) where m and n are the lengths of the 2 strings respectively.

An example usage:

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"]

This is the algorithm implementation. It returns an array of the longest common substring(s). Extended the native String class, so the intersect method is available on all strings.

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

Also need this helper function to create a 2d array with all elements initialize to 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;
}

edited Feb 12, 2010 at 11:19

answered Feb 12, 2010 at 10:15

Anurag

142k37 gold badges223 silver badges262 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Tim Down Over a year ago

Good answer. I had considered implementing this myself but had work to do.

Anurag Over a year ago

@Aruna - glad it worked for you. @Tim - it's fast but lacks simplicity. there's another algorithm that uses suffix trees and takes O(n + m) but not today :)

Tim Down · Accepted Answer · 2011-12-18 00:41:23Z

This isn't very efficient and there are much better ways to do this in general (see @Anurag's answer), but it's simple and works fine for short strings:

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

Brian · Accepted Answer · 2017-05-26 12:30:07Z

0

A simple polyfill of filter a string

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" - case insensitive

"HelloWorld".intersection("HEWOLRLLODo")

"HoWo" - case sensitive

answered May 26, 2017 at 12:30

Brian

1,0361 gold badge17 silver badges26 bronze badges

Collectives™ on Stack Overflow

Javascript string matching pattern help

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related