Problem of the day
You’re given two strings, 'text' of length 'n' and 'pattern' of length 'm', consisting of lowercase characters.
Find all the occurrences of the string ‘pattern’ in ‘text’.
For each occurrence, print the index from where it starts in the string ‘text’ (1 - indexed).
Input: ‘text’ = “cxyzghxyzvjkxyz” and ‘pattern’ = “xyz”
Output: Occurrences = [2, 7, 13]
Explanation: The pattern ‘pattern’ = “xyz” appears at 3 positions in ‘text’.
The first line contains the string ‘text’.
The second line contains the string ‘pattern’.
The first line contains an integer ‘count’, the number of occurrences.
The first line contains ‘count’ integers, the positions of occurrence of ‘pattern’ in ‘text’ in sorted order.
You need not print anything. Return the list of positions in any order. They will be sorted and printed.
cxyzghxyzvjkxyz
xyz
3
2 7 13
The pattern ‘pattern’ = “xyz” appears at 3 positions in ‘text’.
ababacabab
aba
3
1 3 7
Here we have an overlap between the first occurrence (at position 1) and the second occurrence (at position 3), and we are considering both.
abcd
xy
0
The expected time complexity is O(n + m).
1 <= ‘n’ <= 10 ^ 5
1 <= ‘m’ <= ‘n’
Check each substring in ‘text’ of length ‘m’ and see if they are equal to ‘pattern’.
If we find a match we add the current index (1 - based) in our list ‘ans’.
The steps are as follows:
List stringMatch(string ‘text’, string ‘pattern’)
O((n - m) * m), Where ‘n’ and ‘m’ are the lengths of ‘text’ and ‘pattern’ respectively.
The outer loop ‘i’ is running ‘n’ - ‘m’ + 1 times and each inner loop is running ‘m’ times.
Therefore total execution time = (n - m + 1) * m.
Hence the time complexity is O((n - m) * m).
O(1)
We are using constant auxiliary space. The only space we are using is to store the positions of matching occurrences in ‘ans’.
Hence the space complexity is O(1).