a suffix array is just a sorted array of all the suffixes of a given string. The main algorithms include (efficient & inefficient) construction of Suffix Array and how we can use it for substring search & other purposes

Applications

  • Substring Search
  • Bioinformatics
  • Data Compression

Complexity

  • Time: for Naive construction
  • Space:

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

    let word = 'virgo';
const suffixArray = (function skeleton(word) {
  const arr = [];

  for (let i = 1; i <= word.length + 1; i++) {
    arr.push([i, '-']);
  }

  return arr;
}(word));

word += '$'; // special character

console.log('Appended \'$\' at the end of word as terminating (special) character. Beginning filling of suffixes');

function selectSuffix(word, i) {
  let c = i;

  while (i < word.length - 1) {
    
    i++;
  }

  while (c < word.length - 1) {
    
    c++;
  }
  
}

(function createSA(sa, word) {
  for (let i = 0; i < word.length; i++) {
    sa[i][1] = word.slice(i);

    selectSuffix(word, i);
    
  }
}(suffixArray, word));

console.log('Re-organizing Suffix Array in sorted order of suffixes using efficient sorting algorithm (O(N.log(N)))');

suffixArray.sort((a, b) => {
  
  console.log(`The condition a [1] (${a[1]}) > b [1] (${b[1]}) is ${a[1] > b[1]}`);
  
  return a[1] > b[1];
});