Speaker: Vamsi Krishna
Day:  Wednesday, 09/27/2007
Room: ITEB 336
Time: 2:00-3:00pm

Title: Simple Linear Work Suffix Array Construction

Abstract

A suffix array represents the suffixes of a string in sorted
order. Being a simpler and more compact alternative to suffix trees, it
is an important tool for full text indexing and other string processing
tasks. We introduce the skew algorithm for suffix array construction over
integer alphabets that can be implemented to run in linear time using
integer sorting as its only nontrivial subroutine:
1. recursively sort suffixes beginning at positions i mod 3 
= 0.
2. sort the remaining suffixes using the information obtained in step one.
3. merge the two sorted sequences obtained in steps one and two.
The algorithm is much simpler than previous linear time algorithms
that are all based on the more complicated suffix tree data structure.

Reading :
Juha Karkkainen, Peter Sanders: Simple Linear Work Suffix Array
Construction. ICALP 2003,pp. 943-955