Mark Ormesher markormesher

The Skew (Linear Time) Algorithm for Suffix Array Construction

I'll use x = "processing" as an example. Throughout the example * represents the null character, which sorts before any other character (i.e. * < a < b < c < ...).

We start by creating three groups of suffixes - S0, S1 and S2 - so that each suffix in the group Sk starts at the index 3q + k for some value of q. In plain English:

S0 suffixes start at positions 0, 3, 6, etc.
S1 suffixes start at positions 1, 4, 7, etc.
S2 suffixes start at positions 2, 5, 8, etc.

The Doubling Algorithm for Suffix Array Construction

I'll use x = "banana", m = 6 as an example. The suffixes are:

0:  banana
1:  anana
2:  nana
etc.

First, we'll work out R1, which is the rank of each suffix according to it's first letter only. Because we're just comparing single letters, we can do it in Theta(m) with a bucket sort. There will be some duplicates, and that's fine. We only have three different letters, so we give all of the A's a rank of 0, all of the B's a rank of 1, and all of the N's a rank of 2. We end up with this:

	import org.openhab.core.model.script.ScriptServiceUtil

	val heatingZones = newArrayList(
	"livingRoom",
	"bathroom",
	"masterBedroom",
	"spareBedroom",
	"office",
	// etc...
	)

	# input: startingNode

	openList = [] # nodes we have discovered but haven't visited yet
	closedList = [] # nodes we have already visited, store so we don't go back to them

	# if the open list is a stack, we have DFS
	# if the open list is a queue, we have BFS
	# if the open list is a min/max-heap that uses some function of node properties, we have heuristic search
	# the closed list can be a simple set; order is not important

	#!/bin/bash

	# This script needs to go at the root of your source code.
	# This script works with plain old Bash on Ubuntu - YMMV with other shells.
	# You'll need to adjust the extensions and files that are included and ignored.
	# DO NOT run this in the same folder as any other LaTeX work (look at the last line).
	# This script is offered as-is and accept utterly no responsibility for whatever it does.

	texFile="source.tex"
	touch $texFile

	apply plugin: 'com.android.application'

	android {
	compileSdkVersion 23
	buildToolsVersion "23.0.3"

	defaultConfig {
	applicationId "com.example.markormesher.blank_application"
	minSdkVersion 15
	targetSdkVersion 23

	// increment the ID
	++notificationId;

	// create a notification
	NotificationCompat.Builder builder =
	new NotificationCompat.Builder(BasicNotificationActivity.this)
	.setContentTitle("This is notification #" + notificationId)
	.setContentText("This is the text!")
	.setAutoCancel(true)
	.setSmallIcon(R.drawable.kcl_tech_logo)

	import android.database.sqlite.SQLiteDatabase;
	import android.database.sqlite.SQLiteOpenHelper;

	public class DbHelper extends SQLiteOpenHelper {

	public DbHelper(Context context) {
	super(context, Constants.DB_NAME, null, Constants.DB_VERSION);
	}

	@Override

	public class SyncTest {

	public static Obj1 obj1;
	public static Obj2 obj2;

	public static void main(String... args) {
	obj1 = new Obj1();
	obj2 = new Obj2();
	Thread t1 = new Thread(new Runnable() {
	@Override