Eureka!!: Suffix Array

Eureka!!: Suffix Array

I usually don't like to give definitions ( coz i dont remember it :P )
Today i am going to write about a very important data structure called suffix array.

you must have come across problems like finding the
-longest common substring,
-minimum lexicographic rotation of a string,
-finding the longest palindrome, (this can be done in better time by another algorithm)
-searching for a smaller string in a bigger string. ( this can be done in O(m+n) using kmp. however we can do it in O(m log n ) using suffix array. it is useful if we have to search many small strings in the large string. Then it will outspeed KMP)

Read full article from Eureka!!: Suffix Array