Shortest String with Repeated Pattern

Given three inputs S, P, and K, find the shortest string that contains the pattern P at least K times as a contiguous substring. Overlapping occurrences of P are allowed in the final string to minimize its total length.

For instance, if P is "abab", then the string "ababab" contains "abab" twice by reusing the overlapping segment. More generally, if we let O denote the maximum overlap between the suffix and prefix of P, the answer can be constructed as:

( P + (K-1) \times (P[O:]) )

Note: Although an extra string S is provided as input, it is not used in the computation.

inputFormat

The input is read from standard input (stdin) and consists of three lines:

1. The first line contains a string S (this value is not used in the computation).
2. The second line contains the pattern string P.
3. The third line contains an integer K representing the number of times P must appear in the output.

outputFormat

Output a single line to standard output (stdout) containing the shortest string that includes P at least K times as a contiguous substring.

abcde
cde
2

cdecde