F  Random Strings

All submissions for this problem are available.
You are given $2$ string $A$ and $B$ and an integer $K$. You have to find a substring of length $K$ such that it is common in both the strings i.e. present in both String $A$ and $B$. A substring of a string is a contiguous subsequence of that string. For Example, string "bite" is substring of string "biteration", but string "bion" is not. If there are multiple such $K$ length substrings which are present in both $A$ and $B$, then you have to find the one which occurs maximum no of times in both strings combined i.e. the sum of occurrences in both the strings is maximum. If still, there are multiple such $K$ length substrings with max Occurrence and common in both, then u have to find the one which is lexicographically smallest among them. ###Input:  First line contains number of Test Cases $T$.  First line of each Test Case contains $3$ integers $N$, $M$ and $K$, denoting Length of string $A$, length of string $B$ and Length of Common Substring respectively.  Next $2$ lines contains the strings $A$ and $B$ respectively consisting only of lowercase Latin characters. ###Output: For each testcase, in a single line, you have to output the required common substring, or if no such substring exists, output **"1"**(without quotes). ###Constraints  $1 \leq T \leq 20$  $1 \leq N,M \leq 2*10^5$  $1 \leq K \leq min(N,M)$  Sum of $N$ over all test cases does not exceed $2*10^5$  Sum of $M$ over all test cases does not exceed $2*10^5$ ###Subtasks  15 points : $1 \leq N,M \leq 100$  36 points : $1 \leq N,M \leq 1000$  99 points : Original Constraints ###Sample Input: 3 7 6 4 abababc bababa 3 4 1 abb aabb 4 4 3 aabb abab ###Sample Output: abab b 1 ###EXPLANATION: In the first example, "abab" and "baba" are $2$ substrings which are common while "babc" is not. Sum of occurrences of "abab" is 3(2 in A + 1 in B) and of "baba" is also 3(1 in A and 2 in B). So, we need to take the lexicographically smaller among them, which is **abab** In the second example, "a" and "b" are common substrings, but since string "b" has greater sum of occurrences, ans is "b". In the third example, since there is no common substring of length $3$, the ans is "1".Author:  nagpaljatin141 
Editorial  https://discuss.codechef.com/problems/NMN 
Tags  bit22019, hashmap, map, nagpaljatin141, strings, suffixarray 
Date Added:  5082019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 