Problem C
Substring Switcheroo
You and your young daughter have been playing a game to help teach her how to read. She of course loves learning her letters, rearranging them, and asking with each rearrangement, ‘what does this spell?’ Much of the time the letters are nonsense, but sometimes they form a real word.
She is interested in forming really long words, and as such, you have been constructing very long strings of run-together words. She then takes them and adds some letters, removes others, and generally rearranges the letters so that they form something that may be completely different.
You start writing down the strings before and after your daughter has changed them. The question is: what is the largest portion of the original string that was preserved after she edited it, allowing rearrangement of the letters?
For example, if the original string you wrote was fourscoreandsevenyearsago, she might have shuffled all of the letters to make ogasraeynevesdnaerocsruof. The second string is just a rearrangement of the first, so the entire original string was in some way preserved.
However, if she removes the y and adds a z and rearranges the letters again, the string might become reedcuraanonzovresafoegss, and the longest substring of the original that is still a (rearranged) substring in the result is ears (which is rearranged to resa in her version).
Write a program that takes as input two strings: the original one you constructed $A$, and your daughter’s edited version $B$. Find and report the longest substring of $A$ that is a permutation of some substring of $B$. If there are multiple substrings of $A$ that satisfy this criterion with the same length, output the one that appears first in $A$.
Input
Input starts with a line containing an integer $1 \leq n\leq 10$, indicating the number of test cases. Following this are $2n$ lines, each pair representing one test case. The first line of each test case is $A$, the second is $B$. Each string contains between $1$ and $1\, 000$ characters, and uses only the lowercase letters a–z. Within each test case, the two strings have the same length.
Output
Output the longest substring of $A$ that is a permutation of some substring of $B$. If there are multiple longest matches, print the one that occurs earliest in $A$. If there are none, print NONE.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 fourscoreandsevenyearsago ogasraeynevesdnaerocsruof fourscoreandsevenyearsago reedcuraanonyovresafoegss fourscoreandsevenyearsago reedcuraanonzovresafoegss abcdef ghijkl |
fourscoreandsevenyearsago fourscoreandsevenyearsago ears NONE |
