A tutorial on Suffix Arrays

tutorial
, , ,
26

very good explanation…

27

Another nice tutorial :slight_smile:

28

Really Helpful! Cheers :smiley:

29

I am getting wrong suffix array for input
ebbacb

Actual output is

5 3 2 0 4 1

While It should be

3 5 2 1 4 0

30

The N((log N)^2) says “we can use the property that all the strings are related” . But it is not very clear to me that what we are using , can’t we use the same thing for normal string comparison ?

@gamabunta : Will you please help me in explaining that ?

31

My implementation without the LCP array :-

32

Did anyone actually run the C++ SortIndex code? Did it actually give you the correct answer?

I find this line is a bit confusion as after P[stp][previous-position] = i which is a new position after sorting, we lose
track of the actual value that we initialized at the earlier step.

P[stp][L[i].p] =i> 0 && L[i].nr[0]==L[i-1].nr[0] && L[i].nr[1] == L[i- 1].nr[1] ? P[stp][L[i-1].p] : i;

Hence, when the loop starts the next round, all P[stp-1] have is no longer any values related to the original string and sub-strings.
I am puzzling now how this line could make things work they way we think it should be.

Furthermore, the C++ code is exactly in this paper: http://web.stanford.edu/class/cs97si/suffix-array.pdf.

33

Very well explained sir. It will be very helpful for beginners like me.

34

please upvote me

1 Like
35

Awesome Explanation!! :slight_smile:

36

Very Well Written!

37

Video guidance perhaps? dummy here

38

Nicely Explained .Really liked it

39

Thank you very much @kuruma, It took me a while but I got the concept, very nice tutorial :slight_smile:

40

why we are not taking the condition in which L.nr[0]==L.nr[0] and L.nr[1]==L.nr[1] and the answer for this input
ABABBAABB shouldn’t be “5 0 6 2 8 4 1 7 3” but the above code gives 5 0 2 6 4 1 7 3 8 correct me if i am wrong

41

Thanks for this tutorial! I had issues with arrays while working with my coursework help website. This post helped to solve my problems.

42

Can anyone tell me how to print the final answer after verifying locally? I’m trying to learn this algorithm from last one week but no success till now and at this point I don’t feel so good. Please help me understand how matrix P is used.

43

GATTACA
4
1
6
5
0
3
2

Why suffix array for this string is that ? It should be 6 at the first !!!

44

Nice tutorial for start in suffix arrays.

And I really recommend Skew Algorithm. It’s just so awesome and magic, that it takes my breath away first time I saw it :slight_smile:

2 Likes
45

I am glad you liked it @michal27 :slight_smile: I will definitely try to learn Skew’s Algorithm in a not so distant future :slight_smile:

1 Like