SSTORY - Editorial

editorial
, , , , , ,
21

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

22

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

2 Likes
23

One can create many testcases based on above cases…

24

sa_extend in suffix automaton is diificult to understand.

1 Like
25

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

26

Hi! You can see tester’s solution :smiley:

1 Like
27

@rishul_nsit can you please explain this with help of one example.

thankx in advance

28

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

29

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

30

any one please explain extendSA() function

31

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.

32

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

33

This algorithm itself won’t work. We need to separate the 2 strings with a special character.

34

http://lpcs.math.msu.su/~pritykin/csr2008presentations/starikovskaya.pdf

35
36

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 https://www.codechef.com/viewsolution/14290941.