New update is available. Click here to update.

Last Updated: 17 Dec, 2020

Moderate

```
A = “bc”, B = “abcddbc”.
String “A” is present at index 1, and 5(0-based index), but we will return 1 as it is the first occurrence of “A” in string “B”.
```

```
Can you solve this in linear time and space complexity?
```

```
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first and only line of each test case contains two strings A and B, separated by a single space.
```

```
For each test case, print the index of the first occurrence of A in B, if string A is not present in string B then print -1.
```

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= |A|, |B| <= 5 * 10^4
Time limit: 1 second
```

- 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 index
**i**in the range of 0 to N - M, we run another loop from 0 to M. Let’s denote this inner loop counter as**j**. - Then match the characters at (
**i**+**j**)th index of**B**with (**j**)th index of**A**. If at any point characters mismatch, then we break the inner loop and increment**i**by 1. If all these characters match, and we are out of the inner loop, then we return**i**, as it is the index of the first occurrence of**A**in**B**. - If we reach at the end of the outer loop, then we return -1, as
**A**is not present in**B.**

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

- If
- 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.

- If the