TCQF181C - Editorial

PROBLEM LINK:

Contest

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:

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

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

Weak TCs, my brute code passed, link

1 Like