Common Substring (Easy)#5288
Given two strings consisting of the characters and , consider all strings that are substrings of both given strings. Find the -th such common substring in lexicographical order.
A string is considered lexicographically smaller than a string if one of the following conditions is satisfied:
is a prefix of ;
There exists an index , not greater than the lengths of and , such that for all indices j < i, S_j = T_j, and S_i < T_i.
The input consists of three lines. The first and second lines contain the two given strings, each of length at most . The third line contains a positive integer , which does not exceed the number of common substrings of the two given strings.
Output the -th common substring of the two strings in lexicographical order.
Example 1