SSTORY March14

link text this gives me wrong answer of SStory.

second link(link text) gives TLE i am not getting where i am going wrong.

approch:: i just created suffix array and lcp array of (string1+"{"string2) now checking for calue of lcp array such that both index belongs to different range. i don’t know exactly in which test case this is failing…plz someone help…


@antim_patel : Try this case



The suffix array will contain baa… (From 1st string ) , baba… ( from first string ) , bac ( from second string ) , bad from second string .

So if you are examining consecutive entries of SA then you will find a match at “baba” and “bac” and find the index of “ba” as 7 in second string , even though its actually at index 1 also .

Its likely that you may output “yy” instead of “ba” .


sir, my code is giving right answer ba as output, i have handled this type of case also in my code. but instead of this,my code in giving wrong answer.

For this test case: “fagehg”,“fhfgfg” ,your code gives ‘g’ but answer is ‘f’

YOu mean S1=fhfgfg S2=fageh?
otherwise S1=fageh S2=fhfgfg is wrong test case

your test case does satisfy constraints that length of S2<=S1…If i treat s1=fhfgfg and S2=fageh MY code is giving CORRECT Answer …your solution is also failed to pass this case but it is still accepted.
thanks if you have any other case please comment it…thanks

@jangwa … Try to see the essence of the test, take this testcase “fagehg”,“fhfgfg” , now too the answer is wrong.

@antim_patel: Yeah because I went too far in my solution, had I not done some optimizations, I think they sure had a test case which would have failed my solution.

ya man :)…