MINSEQ - Minimal Possible String
Given two strings A and B, your are to find the lexicographically smallest string after inserting B into A.
For example, string A is "369", and string B is "4799". There are 4 ways that I can insert B into A, and I’ll get 4 different results: 4799369, 3479969, 3647999, 3694799. Thus, 3479969 is the lexicographically smallest one.
Input
Input contains several cases. Each case has 2 strings A and B with length no longer than 100000 in 2 lines. Process the input until EOF. The strings consist of only digit 1-9.
Output
For each case, output the minimal possible result.
Example
Input:
369
4799
666
12345
Output:
3479969
12345666
hide comments
Scape:
2021-04-21 00:23:02
Wonderful problem. Also solvable with hashing. |
|
Abhishek pratap singh:
2015-07-28 11:38:05
I am using Suffix Array to rank the suffixes but no getting WA.
|
|
paras meena:
2014-12-24 22:08:22
are u kidding my O((|A|+|B|)*(log(|A|+|B|)^2)) gave TLE o.O and by DC3 i got WA what the hack :/ |
|
ABHISHEK:
2014-05-29 12:29:38
Can anybody give a hint as to how to approach this problem. |
|
Ravi Kiran:
2012-09-21 05:05:49
Really Nice Problem and Good test data! |
|
Buda IM (retired):
2012-09-15 00:22:10
O( |A|log(|A|+|B|) ) is enough to get AC |
|
:D:
2012-06-16 20:50:00
For now I have TLE with O(len(A)+len(B)) so I doubt anything less with give AC.
|
|
Varun Kumar V:
2011-07-14 13:24:01
is this problem solvable in AlogA + B ?? Or even better solution is required ??? |
|
Brainstorm:
2014-01-27 21:10:51
worse problem explanation ever.
|
|
3xian:
2011-06-26 16:54:23
@Xilinx
|
Added by: | 3xian |
Date: | 2009-10-30 |
Time limit: | 1s-1.567s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 PERL6 |
Resource: | GDUT Monthly |