SSTORY - Editorial

editorial
, , , , , ,
13

How can I get all the test cases for this problem? In general does codechef publish test cases for the challenge problems?

14

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

3 Likes
15

sa_extend in suffix automaton is diificult to understand.

1 Like
16

Please provide a c++ code link for binary search and hashing solution …

17

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

18

can any one please explain me what is happening in sa_extend?
It would be a great help.

19

any one please explain extendSA() function

20

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.

21

Another solution using Suffix Array can be found here : http://www.roman10.net/2012/03/16/suffix-array-part-3-longest-common-substring-lcs/

22
23

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.

24

Problems like these are the reason I love Codechef long contest. Educative problem backed by a superb editorial.

5 Likes
25

I agree with you. The setter want me to emphasize the Suffix Automaton. So I omit the Suffix Array solution.

2 Likes
26

Those 2 pages of wrong answers taught me a lot of new things :slight_smile: by the HARD way… Grats to bruno!

2 Likes
27

Try going trough this link, maybe it will help you out:
http://discuss.codechef.com/questions/39834/wa-in-sstory-suffix-arrays

28

@kuruma Thanks but my code works on all the test cases mentioned there. Can you provide some tricky case?

29

Try to look at my code along with explanation :slight_smile:

30

Check your solution for this test case s1=“aecd” and s2=“acad” … the answer should be a but your solution gives c…

1 Like
31

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.

3 Likes
32

One can create many testcases based on above cases…