I got AC after considering these two testcases
abcadlfghijkl
abcdlfabcde
Answer is 3 abc and not 3 dlf
similarly ,
abcmdefghijkl
abcdefabcdl
Answer is 3 abc and not 3 def
I got AC after considering these two testcases
abcadlfghijkl
abcdlfabcde
Answer is 3 abc and not 3 dlf
similarly ,
abcmdefghijkl
abcdefabcdl
Answer is 3 abc and not 3 def
sa_extend in suffix automaton is diificult to understand.
Please provide a c++ code link for binary search and hashing solution …
I go through this sa_extend() function but i am getting difficulties to understand it.
can anyone please elaborate it in more specific way.
Thanks
can any one please explain me what is happening in sa_extend?
It would be a great help.
any one please explain extendSA() function
Is Suffix Automaton explained in any book/resource in more formal way rather than code ?
I am confused because we don’t have fixed string to create an automaton.
Another solution using Suffix Array can be found here : http://www.roman10.net/2012/03/16/suffix-array-part-3-longest-common-substring-lcs/
How to find LCS given Suffix Automaton? If the first character of the pattern doesn’t exist in the text, how would the state change?
Btw, my solution with Suffix Arrays gets TLE CodeChef: Practical coding for everyone.
Problems like these are the reason I love Codechef long contest. Educative problem backed by a superb editorial.
I agree with you. The setter want me to emphasize the Suffix Automaton. So I omit the Suffix Array solution.
Those 2 pages of wrong answers taught me a lot of new things by the HARD way… Grats to bruno!
Try going trough this link, maybe it will help you out:
http://discuss.codechef.com/questions/39834/wa-in-sstory-suffix-arrays
@kuruma Thanks but my code works on all the test cases mentioned there. Can you provide some tricky case?
Try to look at my code along with explanation
Check your solution for this test case s1=“aecd” and s2=“acad” … the answer should be a but your solution gives c…
We can still have the other approach mentioned. The Editorial should be as elaborate as possible and may capture multiple ways of solving the problem. It is also made a community wiki so that anyone can edit/add to it.
One can create many testcases based on above cases…
Hi! You can see tester’s solution