Last Updated: 17 Dec, 2020

Implement strStr()

Moderate

Asked in companies

Solve now

Problem statement

You are given two strings A and B. Find the index of the first occurrence of A in B. If A is not present in B, then return -1.

For Example:

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

Follow Up:

Can you solve this in linear time and space complexity?

Input format:

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.

Output format:

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.

Note:

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

Constraints:

1 <= T <= 100
1 <= |A|, |B| <= 5 * 10^4 

Time limit: 1 second

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

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.

Solve now