Merge pull request algorithm-visualizer#131 from duaraghav8/gh-pages

Raghav Dua · Raghav Dua · commit 75a62333d240 · 2016-06-01T21:37:10.000+05:30
Suffix Array Construction (naive)
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -59,7 +59,8 @@
     "list": {
       "edit_distance": "Edit Distance",
       "knuth_morris_pratt": "KMP Substring Search",
-      "rabin_karp_algorithm": "Rabin-Karp Algorithm"
+      "rabin_karp_algorithm": "Rabin-Karp Algorithm",
+      "suffix_array": "Suffix Array (construction & usage)"
     }
   },
   "dp": {
diff --git a/algorithm/string/suffix_array/construction_naive/code.js b/algorithm/string/suffix_array/construction_naive/code.js
@@ -0,0 +1,42 @@
+word += '$';	//special character
+logger._print ('Appended \'$\' at the end of word as terminating (special) character. Beginning filling of suffixes');
+
+function selectSuffix (word, i) {
+	var c = i;
+
+	while (i < word.length-1) {
+		wordTracer._select (i);
+		i++;
+	}
+	wordTracer._wait ();
+
+	while (c < word.length-1) {
+		wordTracer._deselect (c);
+		c++;
+	}
+	wordTracer._wait ();
+}
+
+(function createSA (sa, word) {
+	for (var i = 0; i < word.length; i++) {
+		sa [i] [1] = word.slice (i);
+
+		selectSuffix (word, i);
+		saTracer._notify (i, 1, sa [i] [1])._wait ();
+		saTracer._denotify (i, 1)._wait ();
+	}
+}) (suffixArray, word);
+
+logger._print ('Re-organizing Suffix Array in sorted order of suffixes using efficient sorting algorithm (O(N.log(N)))');
+suffixArray.sort (function (a, b) {
+	logger._print ('The condition a [1] (' + a [1] + ') > b [1] (' + b [1] + ') is ' + (a [1] > b [1]));
+	return a [1] > b [1];
+});
+
+for (var i = 0; i < word.length; i++) {
+	saTracer._notify (i, 0, suffixArray [i] [0]);
+	saTracer._notify (i, 1, suffixArray [i] [1])._wait ();
+
+	saTracer._denotify (i, 0);
+	saTracer._denotify (i, 1);
+}
diff --git a/algorithm/string/suffix_array/construction_naive/data.js b/algorithm/string/suffix_array/construction_naive/data.js
@@ -0,0 +1,17 @@
+var word = 'virgo';
+var suffixArray = (function skeleton (word) {
+	var arr = [];
+
+	for (var i = 1; i <= word.length+1; i++) {
+		arr.push ([i, '-']);
+	}
+
+	return arr;
+}) (word);
+
+var saTracer = new Array2DTracer ('Suffix Array'),
+	wordTracer = new Array1DTracer ('Given Word'),
+	logger = new LogTracer ('Progress');
+
+saTracer._setData (suffixArray);
+wordTracer._setData (word);
diff --git a/algorithm/string/suffix_array/desc.json b/algorithm/string/suffix_array/desc.json
@@ -0,0 +1,18 @@
+{
+  "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",
+  "Applications": [
+    "Substring Search",
+    "Bioinformatics",
+    "Data Compression"
+  ],
+  "Complexity": {
+    "time": " O(N<sup>2</sup>.log(N)) for Naive construction",
+    "space": "O(N<sup>2</sup>)"
+  },
+  "References": [
+    "<a href='https://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays'>Codechef</a>"
+  ],
+  "files": {
+    "construction_naive": "Suffix Array inefficient construction"
+  }
+}
