Posted: 17 Dec, 2020
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.
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.
Most Frequent Element
Posted: 25 Feb, 2022
Shortest Common Supersequence
Posted: 4 Mar, 2022
Posted: 13 Apr, 2022
Posted: 14 Apr, 2022
Posted: 15 Apr, 2022