LCP Maximization

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given two strings S and T each consisting of n characters. Each character in both the strings is one of the first ten Latin lowercase alphabet letters ('a''j'). The characters are numbered 1 through n in both strings. Let's denote S[l..r] as a substring of S which begins at the l'th character of S and ends at the r'th character of S.
Longest common prefix (LCP) of two strings is the longest prefix of the first string which is also a prefix of the second.
You are asked to process q queries of the following kind:
You are given two integers x and y (1 ≤ x, y ≤ n). Your task is to find the length of the LCP of S[x..n] and T[y..n]. You are allowed to apply some permutation to all of the distinct letters of S before finding the LCP. More formally, you should make a bijection from letters 'a''j' to the same set of letters, replace each letter of S with the corresponding value in the bijection and then find the LCP. You should pick the bijection so that the LCP is as large as possible. If there are several possible bijections, you should pick the one with the least possible letter assigned to 'a', then (if still ambiguous) to 'b' and so on.
Please note that the changes in S doesn't propagate over queries, i.e. all the string transformations are only within a single query and should be rolled back before processing the next one.
Input
The first line of the input contains one integer T denoting the number of test cases.
The first line of the test case description contains two integers n and q. The next two lines contain two string S and T respectively. Each of the next q lines contains two integers x and y denoting a query to process.
Output
For each of the queries, output the length of the LCP together with the optimal bijection in the format "{the letter assigned to 'a'}{the letter assigned to 'b'}...{the letter assigned to 'j'}".
Constraints
 1 ≤ T ≤ 5
 1 ≤ n ≤ 125000
 1 ≤ q ≤ 50000
Example
Input: 1 5 3 ababa babaa 1 1 1 3 5 4 Output: 4 bacdefghij 2 bacdefghij 1 abcdefghij
Author:  kostya_by 
Tester:  pavel1996 
Editorial  http://discuss.codechef.com/problems/LCPMAX 
Tags  cook69, kostya_by, medium 
Date Added:  26032016 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions