Implement strstr() function in C
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

Question

Implement strstr() function in C

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

Accepted Answer

Iterative implementation of strstr(): It returns a pointer to the first occurrence of Y in X or a null pointer if Y is not part of X. The time complexity of this solution is O(m.n) where m and n are the length of String X and Y, respectively.

// returns true if `X` and `Y` are the same

int compare(const char *X, const char *Y)
{
	while (*X && *Y)
	{
		if (*X != *Y) {
			return 0;
		}
		X++;
		Y++;
	}
		return (*Y == '\0');
}

	// Function to implement `strstr()` function
const char* strstr(const char* X, const char* Y)
{
	while (*X != '\0')
	{
		if ((*X == *Y) && compare(X, Y)) {
			return X;
		}
		X++;
	}
	return NULL;
}

Accepted Answer

Brute-force

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.

Space Complexity: O(1)Explanation:

O(1).

Constant extra space is required.

Time Complexity: O(1)Explanation:

O(N * M), where N is the length of the string B and M is the length of string A.

In the worst case, we will be traversing the whole string B, and for each index of B, we will traverse the string A. Hence the time complexity is O(N * M).

Accepted Answer

KMP Algorithm

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.

Space Complexity: O(n)Explanation:

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

Time Complexity: O(n)Explanation:

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