GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Suffix Array Construction (naive) · allensh929/AlgorithmVisualizer@081a9e0

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • algorithm
    • category.json
    • string/suffix_array
      • construction_naive
        • code.js
        • data.js
      • desc.json
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎algorithm/category.json‎

Copy file name to clipboardExpand all lines: algorithm/category.json
+2-1Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,8 @@
5959
"list": {
6060
"edit_distance": "Edit Distance",
6161
"knuth_morris_pratt": "KMP Substring Search",
62-
"rabin_karp_algorithm": "Rabin-Karp Algorithm"
62+
"rabin_karp_algorithm": "Rabin-Karp Algorithm",
63+
"suffix_array": "Suffix Array (construction & usage)"
6364
}
6465
},
6566
"dp": {
Collapse file

‎algorithm/string/suffix_array/construction_naive/code.js‎

Copy file name to clipboard
+42Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
word += '$'; //special character
2+
logger._print ('Appended \'$\' at the end of word as terminating (special) character. Beginning filling of suffixes');
3+
4+
function selectSuffix (word, i) {
5+
var c = i;
6+
7+
while (i < word.length-1) {
8+
wordTracer._select (i);
9+
i++;
10+
}
11+
wordTracer._wait ();
12+
13+
while (c < word.length-1) {
14+
wordTracer._deselect (c);
15+
c++;
16+
}
17+
wordTracer._wait ();
18+
}
19+
20+
(function createSA (sa, word) {
21+
for (var i = 0; i < word.length; i++) {
22+
sa [i] [1] = word.slice (i);
23+
24+
selectSuffix (word, i);
25+
saTracer._notify (i, 1, sa [i] [1])._wait ();
26+
saTracer._denotify (i, 1)._wait ();
27+
}
28+
}) (suffixArray, word);
29+
30+
logger._print ('Re-organizing Suffix Array in sorted order of suffixes using efficient sorting algorithm (O(N.log(N)))');
31+
suffixArray.sort (function (a, b) {
32+
logger._print ('The condition a [1] (' + a [1] + ') > b [1] (' + b [1] + ') is ' + (a [1] > b [1]));
33+
return a [1] > b [1];
34+
});
35+
36+
for (var i = 0; i < word.length; i++) {
37+
saTracer._notify (i, 0, suffixArray [i] [0]);
38+
saTracer._notify (i, 1, suffixArray [i] [1])._wait ();
39+
40+
saTracer._denotify (i, 0);
41+
saTracer._denotify (i, 1);
42+
}
Collapse file

‎algorithm/string/suffix_array/construction_naive/data.js‎

Copy file name to clipboard
+17Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
var word = 'virgo';
2+
var suffixArray = (function skeleton (word) {
3+
var arr = [];
4+
5+
for (var i = 1; i <= word.length+1; i++) {
6+
arr.push ([i, '-']);
7+
}
8+
9+
return arr;
10+
}) (word);
11+
12+
var saTracer = new Array2DTracer ('Suffix Array'),
13+
wordTracer = new Array1DTracer ('Given Word'),
14+
logger = new LogTracer ('Progress');
15+
16+
saTracer._setData (suffixArray);
17+
wordTracer._setData (word);
Collapse file

‎algorithm/string/suffix_array/desc.json‎

Copy file name to clipboard
+18Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
{
2+
"Suffix Array": "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",
3+
"Applications": [
4+
"Substring Search",
5+
"Bioinformatics",
6+
"Data Compression"
7+
],
8+
"Complexity": {
9+
"time": " O(N<sup>2</sup>.log(N)) for Naive construction",
10+
"space": "O(N<sup>2</sup>)"
11+
},
12+
"References": [
13+
"<a href='https://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays'>Codechef</a>"
14+
],
15+
"files": {
16+
"construction_naive": "Suffix Array inefficient construction"
17+
}
18+
}

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.