PROBLEM LINK:
DIFFICULTY:
EASY
PREREQUISITES:
Strings, KMP, C++ STL
PROBLEM:
Find the first and last occurence of substring F in string S. Based on the index found, output the hour division which it belongs.
EXPLANATION:
The solution has a very simple trick with KMP algorithm.
Given string S and substring F, KMP algorithm will preprocess and find the occurences of F in S in O(n+m) time where n is length of string S and m is length of string F.
After finding the occurences of string F in S, there are following conditions which will occur:
- String F has atleast 2 occurences:
After finding first and last occurence of string F in S, the hour can be found easily by (first/X)+1 and (last/X)+1 provided the indexing of the string is 0 based.
- String F has less than 2 occurences:
The answer will be -1 since to mention first and last occurence of string F in S, we need atleast 2 occurence of the same.
LINKS
KMP Algorithm: Link
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here