### 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