Substring Switcheroo

Photo by
lylamerle

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 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 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 |