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.

CodePudding user response：

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