CODEWITHSUNDEEP
javascript
Irfan Ansari
Irfan Ansari

Reputation: 13

bruteforce string matching javascript

  function search(pattern, text) {
            var M = pattern.length;
            var N = text.length;
            for (var i = 0; i < N - M; i++) {
                var j =0;
                while (j < M) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {break;}
                }
                if (j == M) {return i;}
            }
            return -1;
        }

        console.log(search("rf", "jdsrfan"));

I want to make an brute-force string matching algorithm in JavaScript. Can anyone tell me whats wrong with above code?

I did fixed it myself fixed code as follows:

// return offset of first match or -1 if no match
function bruteForcePatternSearch(sPattern, sText) {
    var M = sPattern.length,
        N = sText.length;
    for (var i = 0; i <= N - M; i++) {
        var j=0;
        while (j < M) {
            if (sText.charAt(i+j) !=sPattern.charAt(j)){
                break;
                }
        j++;
            }
        if (j == M) {return i;}            // found at offset i
    }
    return -1;                            // not found
}

bruteForcePatternSearch("abracadabra","abacadabrabracabracadabrabrabracad");

Upvotes: 0

Views: 2409

Answers (2)

Alex Shesterov
Alex Shesterov

Reputation: 27565

You're never incrementing j to start with. Hence the infinite loop.

Then, as Claudio commented, i < N - M is wrong. Should be i <= N - M.

Spoiler: here the fixed function. But I advise you not to take it as-is, but to try doing it yourself instead. 

function search(pattern, text) {
        var M = pattern.length;
        var N = text.length;
        for (var i = 0; i <= N - M; ++i) {
            var matched = true;
            for (var j = 0; j < M; ++j) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    matched = false;
                    break;
                }
            }
            if (matched) {
                return i;
            }
        }
        return -1;
    }

Upvotes: 3

Sufyan Jamil
Sufyan Jamil

Reputation: 54

i guess this will work 

for (var i = 0; i < M; i++) {
            var j =0;
            while (j < N) {
                if (text.charAt(j) != pattern.charAt(i)) {
                     break;
                     }
                 j++
            }
            if (j == M) {return i;}
        }

here is the explanation

on each pattern match each character of text

Upvotes: 0

Related Questions