petar-dambovaliev

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.

petar-dambovaliev

package main

import (
	"log"
	"net"
	"os"
	"os/signal"
	"sync"
	"syscall"
	"time"