Example Program
Suffix Array
Example for how to create a suffix array and use it as a dictionary.
Given a sequence s, a suffix array is an array containing start positions of all suffices of s in lexicographical order. A suffix array can simply be used to find all occurrences of an arbitrary substring t in s in O(|t|*log(|s|)).
SeqAn contains various suffix array construction algorithms like the Skew algorithm (J. Karkkainen and P. Sanders, "Simple Linear Work Suffix Array Construction", 2003), a more efficient modification of the Skew algorithm (difference cover of 7), external memory Skew algorithms, the prefix-doubling algorithm (U. Manber and G. Myers, "Suffix arrays: A new method for online string searching", 1993), the algorithm of Larsson and Sadakane (N.J. Larsson and K. Sadakane, "Faster Suffix Sorting", 1999), and a quicksort based algorithm.
The following example constructs a suffix array using the modified Skew algorithm and searches the interval of suffices beginning with t="l". The start positions of these suffices are the occurences of t, which are outputted at last. This is only an example for createSuffixArray and similar functions. For an index based substring search better use the more generic Finder class (see Index Finder demo).
File "index_sufarray.cpp"
A tutorial about suffix arrays.
1#include <iostream>
2#include <seqan/index.h>
3
4using namespace seqan;
5
6int main ()
7{
8    String<char> text = "hello world!";
9    String<char> pattern = "l";
10    String<unsigned> sa;
11
Build a suffix array using the Skew7 algorithm.
12    resize(sa, length(text));
13    createSuffixArray(sa, text, Skew7());
14
Search the interval of suffices beginning with the pattern.
15    Pair<unsigned> hitRange;
16    hitRange = equalRangeSA(text, sa, pattern);
17
Output the suffix indices, i.e. the occurrences of the pattern.
18    for(unsigned i = hitRange.i1; i < hitRange.i2; ++i)
19        ::std::cout << sa[i] << " ";
20    ::std::cout << ::std::endl;
21 
22    return 0;
23}
Output
weese@tanne:~/seqan$ cd demos
weese@tanne:~/seqan/demos$ make index_sufarray
weese@tanne:~/seqan/demos$ ./index_sufarray
9 2 3
weese@tanne:~/seqan/demos$
SeqAn - Sequence Analysis Library - www.seqan.de