• If the length of B is less than the length of A, then we simply return -1.
• Now let’s denote the length of A as M and the length of B as N.
• Now, we run a loop from 0 to N - M and for each inde...read more

In the brute force approach, for each index of the string B, we check for the next M characters, and whenever we find a mismatch, we move one index ahead in string B. By doing this, we may have to check for the same characters again and again and the time complexity increases to O(N * M) in the worst case, where M and N are the lengths of strings A and B respectively.

However, by using the KMP algorithm, we precompute the LPS(Longest Proper Prefix that is also a Suffix) array of length M. So, we already know some of the characters in the next window. In this way, we avoid checking the same matching characters again and again.

• If the length of B is less than the length of A, then we simply return -1.
• We first compute the LPS array i.e call the function i.e kmpPreProcess(A, M).
• Keep two pointers i and j. Initialise both of them to 0.
• Run a loop while i is less than N and j is less than M, where M and N are the lengths of A and B respectively.
• If the ith character of B matches with the jth character of A, then increment both i and j.
• If the ith character of B doesn’t match with the jth character of A, then check the value of j i.e
  • If j > 0, then j redirects to lps[j - 1]. Else, increment i by
• Finally, when we come out of the loop, then check whether the value of j is equal to M. If j is equal to M, then return i - j, else return -1.

For calculating the lps array:

• Create an lps array of size M, where M is the length of string A and initialize all elements in the array to 0.
• Keep two pointers i and j. Initialise i as 1 and j as 0.
• Run a loop till i < M, and do:
  • If the ith index of A matches with the jth index of A, then store the value j + 1 at lps[i] and increment both i and j.
  • If the ith index of A doesn’t match with the jth index of A, then check whether j > 0. If j > 0, then j redirects to lps[j - 1], else mark lps[i] as 0 and increment i by 1.

O(M), where M is the length of the string A.

In the worst case, we are creating the lps array of size M, Hence the overall space complexity will be O(M).

O(N + M), where M and N are the lengths of the string A and B respectively.

In the worst case, we will be traversing the whole string A and B, but since the lps array for A is already calculated, so the value of j just redirects to lps[j - 1] if any mismatch occurs. Hence the overall complexity will be O(N + M).

let a = 'bc';

let b = 'abcddbc';

let bArray = b.split("");

let aArray = a.split("");

console.log(bArray);

var flag = 0;

for(let i=0; i

if(bArray[i] == aArray[0] && bArray[i+1] == aArray...read more