SSTORY - Editorial

editorial
, , , , , ,
7

@author
I appreciate other approaches mentioned in this editorial but can you provide some tricky cases where the usual Suffix Array solution would fail. I have been continuously getting WA with that approach.

Thanks.

3 Likes
8

I did something a bit different. What I did was create the generalized suffix tree of s1 and s2, and look for a node with greatest depth that had a leaf from s1 and a leaf from s2 (breaking ties minimizing the index of the node, which is when it was first added). This runs in linear time overall (linear time for creating the suffix tree, then linear time for a DFS). I believe this is the “standard” “textbook” way of doing it with suffix trees, since I remember talking about this in my computational biology class.

7 Likes
9

Can you give a little details of

int q = st [ p ] . next [ c ] ;
if ( st [ p ] . len + 1 == st [ q ] . len )
st [ cur ] . link = q ;

10

can any one provide some tricky test case

11

I used the suffix array, lcp approach. And then searched for the max lcp between consecutive elements in suffix array such that they come from different strings.
I got WA if anyone can help me out where I went wrong, I will be grateful. :slight_smile:
Here is my effort
http://www.codechef.com/viewplaintext/3611533

12

I tried it using Rabin-Karp hash but am not able to get my solution accepted.
So can anybody explain tester’s solution?
What are vis[], head[], nextcell[]… etc. used for ??
What do mark and cnt denote ??
How do insert() and check() work ??
It is very difficult to decipher such a code without a single comment.

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