IITWPC4H - Maggu and Cuteness of Strings
Given two strings s and t of size n and m respectively. You can construct a string w of size n+m using s and t such that it should contain both s and t as its subsequences.
String w must satisfy this condition: For each character from 'a' to 'z', count of the character in w should be equal to sum of count in s and t. Additionally every character of w must belong to the subsequence for either s or t.
e.g. if s = ab and t = cd, Then w can be abcd, acbd, cdab, cabd, acdb, cadb. Note that adcb is not correct, As t is not a subsequence in it.
“Cuteness value” of a string is defined as the maximum length of consecutive equal characters in the string.
For all possible string w that you can construct, find out the maximum value of “Cuteness value”.
Input
First line contains T: number of test cases.
For each test you case you are given a single line containing two space separated strings s and t. (1 <= size(s), size(t) <= 10^5).
Both the strings s and t will have characters from 'a' to 'z' of English alphabet only.
Note: Sum of length of all the input string is less than 5*10^6.
Output
For each test case, output the answer as given in problem statement.
Example
Input: 1 ab ab Output: 2
hide comments
Jacob Plachta:
2014-03-03 06:49:23
If s=t="abab", can we have w="ababbbaa", for example? This seems to meet the stated requirements, but I'm guessing it's intended that every character of w must belong to the subsequence for either s or t?
|
Added by: | praveen123 |
Date: | 2014-02-03 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | IITK ACA CSE online judge |