Search if a string contains a substring in Javascript (partial search)

Question

Yes I know we can use indexOf and includes or a regular expression to find weather a string is present in another string.

But we have a different requirement. We would like indexOf or includes function to return true even if partial string is matched not the whole world. Let me provide an example.

Let's say my username is "Animation". The string the I am entering is "sssrtAnimyt5678". Now as the string "sssrtAnimyt5678" contains "Anim" which is present in "Animation" we want the function to return true.

The problem with indexOf, includes and regular expression is it tries to find the whole word "Animation" but not the partial word "Anim". I even used KMP Algorithm and found out that even KMP searches for "Animation" not "Anim". Below is the implementation of KMP in Javascript.

    var makeKMPTable = function(word) {
    if(Object.prototype.toString.call(word) == '[object String]' ) {
        word = word.split('');
    }
    var results = [];
    var pos = 2;
    var cnd = 0;

    results[0] = -1;
    results[1] = 0;
    while (pos < word.length) {
        if (word[pos - 1] == word[cnd]) {
            cnd++;
            results[pos] = cnd;
            pos++;
        } else if (cnd > 0) {
            cnd = results[cnd];
        } else {
            results[pos] = 0;
            pos++;
        }
    }
    return results;
};

var KMPSearch = function(string, word) {
    if(Object.prototype.toString.call(string) == '[object String]' ) {
        string = string.split('');
    }
    if(Object.prototype.toString.call(word) == '[object String]' ) {
        word = word.split('');
    }

    var index = -1;
    var m = 0;
    var i = 0;
    var T = makeKMPTable(word);

    while (m + i < string.length) {
        if (word[i] == string[m + i]) {
            if (i == word.length - 1) {
                return m;
            }
            i++;
        } else {
            m = m + i - T[i];
            if (T[i] > -1) {
                i = T[i];
            } else {
                i = 0;
            }
        }
    }
    return index;
};
console.log(KMPSearch("sssrtAnimyt5678", "Animation")); // returns -1

So I would like to know if such kind of partial search is possible and if anybody can point me to such implementation details or algorithm it would be helpful.

Thanks in Advance.

If your username is `Animation` and you enter `noob`, should that be a match, because `n` is in `Animation`? — Andrew Parks, Feb 01 '23 at 17:20
There's some details of what you're trying to do that might get you caught. First, what if my username is A. Then my password can't contain any A's. There probably needs to be a minimum length to search. There's also case sensitivity to consider. Once those two are resolved. I would highly recommend implementing the check as a loop that tests from minimum length to total length using indexOf. I advise against a really clever regex in this case because it will be difficult to read and understand if they need to maintain the code in the future. — NetByMatt, Feb 01 '23 at 17:21
Thanks guys I did not consider these scenarios and now understand that a minimum length is required. — Abhilash D K, Feb 01 '23 at 17:25
for string comparison like this, it might be worth reading about [fuzzy search](https://stackoverflow.com/questions/32337135/fuzzy-search-algorithm-approximate-string-matching-algorithm) — async await, Feb 01 '23 at 17:27
are you sure, you want to get only a boolean value, if the check stops as looking for `'A'` only? — Nina Scholz, Feb 01 '23 at 17:36

score 3 · Accepted Answer · answered Feb 01 '23 at 17:37

3

Just check any possible substring.

const
    hasCommon = (a, b) => {
        for (let i = 0; i < a.length; i++) {
            for (let j = i + 1; j <= a.length; j++) {
                if (b.includes(a.slice(i, j))) return true;
            }
        }
        return false;
    };
    
console.log(hasCommon('Animation', 'sssrtAnimyt5678'));

answered Feb 01 '23 at 17:37

Nina Scholz

376,160
25
347
392

Thank you this works for our scenario. Let me check with an email address too. – Abhilash D K Feb 01 '23 at 17:39
But as you specified `hasCommon("sssrtAnimyt5678", "A")` will also return true. Now we are in a pickle :P – Abhilash D K Feb 01 '23 at 17:44
I beleive we need to set some minimum length. – Abhilash D K Feb 01 '23 at 17:45
@ NinaScholz I think for our scenario `hasCommon("sssrtAnimyt5678", "A")` this situation never occurs as the second parameter is being fetched from DB and it will always be more than 5 characters. So thanks again. I need to do more DSA lol. – Abhilash D K Feb 01 '23 at 17:49

Search if a string contains a substring in Javascript (partial search)

1 Answers1