SPOJ.com - Problem MINSEQ

MINSEQ - Minimal Possible String

no tags

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

Submit solution!

hide comments

< Previous 1 2 Next >

	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. I have tried these test cases 987 9876 8769 9876 657 6567 Last one was the most tricky one that I could think of :/ Can anyone help me?
	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. EDIT: My bad. Due to bad algo, complexity was much higher. Got 0.41 with actual O(len(A)+len(B)) (some I/O optimization included). Last edit: 2012-11-24 21:19:14
	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. I did understand what is written, and I'm quite sure my code works, still, it tells me the 'wrong answer' error. Are we supposed to guess hidden rules? ------- 3xian: Sometimes python would crash on SPOJ when using large memory. But your submissions which got 'wrong answer' are really wrong, please check them carefully. Last edit: 2012-06-03 09:47:15
	3xian: 2011-06-26 16:54:23 @Xilinx It is caused by ASCII 13 and 10, but not redundant empty lines. Anyway, “scanf()” is recommended. Last edit: 2010-02-12 08:58:59

Submit solution!

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