A tutorial on Suffix Arrays

tutorial
, , ,
21

I am a beginner. Very well written sir. It was a deep and helpful insight.

1 Like
22

I think the final answer given is wrong. It should be

sort-Index Suffix-Index

0       10: i
1        7: ippi
2        1: ississippi
2        4: issippi
3        0: mississippi
4        9: pi
5        8: ppi
6        6: sippi
7        3: sissippi
8        5: ssippi
9        2: ssissippi
23

This was awesome!
Thanks Bruno.

24

while sorting the suffixes according to the first 4 characters, why is “3” not assigned in the second tuple ??

25

shouldn’t in the naive approach

for(int i = 0; i < s.size();i++)
{
    m[s.substr(i,s.size()-i)] = i;
    v.push_back(s.substr(i,s.size()-i));
}

should be:

for(int i = 0; i < s.size();i++)
{
    m[s.substr(i,s.size()-1)] = i;
    v.push_back(s.substr(i,s.size()-1));
}

???

notice the size() - 1 instead of size()-i

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