String Algorithms

Strings in Go

A Go string is an immutable sequence of bytes. s[i] is a byte, len(s) counts bytes, and slicing s[i:j] shares memory and costs O(1). Text in UTF-8 may use several bytes for one character, and for _, r := range s decodes runes. The algorithms in this lesson work on positions, so they treat a string as a sequence of bytes: correct for ASCII and for any byte data. For text with multi-byte characters, convert with []rune(s) first, run the algorithm on the runes, and remember that positions are then rune positions.

The Toolbox

For everyday use, the standard library's strings.Index, strings.Contains and regexp are the right choice. The algorithms here are what you reach for when the library does not fit: many patterns, streaming input, a text that is queried thousands of times, or a problem that is not a plain search at all. They also teach a technique that recurs everywhere: keep what you already learned and never start over.

Pattern Matching

Find every position where a pattern of length m occurs in a text of length n, matches allowed to overlap. The demo 64_pattern_matching.go implements four methods, counts character comparisons, and checks all of them against strings.Index on 5,000 random inputs.

The Naive Method

Try every start position, compare from the left, stop at the first mismatch. It is simple and fast on typical text, where a mismatch comes after one or two characters. Its worst case is a text of a repeated letter and a pattern that almost matches: for a^100000 and the pattern a^999 b it makes 99,001,000 comparisons, because each start position matches 999 characters before failing, and then everything is compared again from the next position. That waste is what the next algorithms remove.

The Prefix Function

When a mismatch happens after some characters matched, those characters are a prefix of the pattern. The prefix function stores, for every position i, the length of the longest proper prefix of pattern[:i+1] that is also a suffix of it. Such a prefix-and-suffix is called a border. For abcabd the values are 0 0 0 1 2 0: after reading abcab the border is ab, of length 2.

After the mismatch the pattern slides by 5 − pi[4] = 3. The text pointer stays where it is.

func prefixFunction(p string) []int {
	pi := make([]int, len(p))
	k := 0 // length of the border of p[:i] that we are trying to extend
	for i := 1; i < len(p); i++ {
		for k > 0 && p[i] != p[k] {
			k = pi[k-1] // try the next shorter border
		}
		if p[i] == p[k] {
			k++
		}
		pi[i] = k
	}
	return pi
}

The function looks like it has a loop inside a loop, but it is O(m): k rises by at most one per character, and every fall-back lowers it, so the total number of fall-backs cannot exceed the total number of increases. This "amortized" argument is the same one that makes a dynamic array's append cheap. The demo prints [0 1 0 1 2 2 3] for aabaaab, and [0 0 0 1 2 3 4 5 6] for abcabcabc.

Knuth-Morris-Pratt

KMP scans the text once with the same fall-back loop. k is the number of pattern characters currently matched. On a mismatch, k falls back to the longest border, and the text position does not move. After a full match, the search continues from the border, so overlapping matches are found.

	pi := prefixFunction(pat)
	k := 0
	for i := 0; i < len(text); i++ {
		for k > 0 && text[i] != pat[k] {
			*cmps++
			k = pi[k-1]
		}
		*cmps++
		if text[i] == pat[k] {
			k++
		}
		if k == len(pat) {
			res = append(res, i-k+1)
			k = pi[k-1]
		}
	}

Since the text pointer only moves forward, the scan is O(n), and with the O(m) table the total is O(n + m) for every input. The demo counts *cmps to show the difference: on the worst case above, KMP makes 199,001 comparisons against the naive 99,001,000.

The Z-Function

A second table with the same power. z[i] is the length of the longest common prefix of the string and its suffix starting at i. The window [l, r) is the rightmost part already known to match a prefix; inside it, z[i] can be copied from z[i-l] instead of compared again.

func zFunction(s string) []int {
	z := make([]int, len(s))
	l, r := 0, 0
	for i := 1; i < len(s); i++ {
		if i < r {
			z[i] = min(r-i, z[i-l])
		}
		for i+z[i] < len(s) && s[z[i]] == s[i+z[i]] {
			z[i]++
		}
		if i+z[i] > r {
			l, r = i, i+z[i]
		}
	}
	return z
}

To search, compute z for pattern + separator + text. Any position where z equals the pattern length is an occurrence, and the separator (a byte found in neither string) stops a match from running across the seam. For aabxaab the demo prints [0 1 0 0 3 1 0]: the suffix at position 4 shares three characters with the whole string. Prefix function and Z-function are interchangeable for most problems; use whichever one you can write from memory.

Horspool: Skipping Text

Both tables above still read every text character. Horspool compares the window from its right end and then slides the window by a distance that depends only on the text character under the window's last cell: how far that character is from the end of the pattern, or the full pattern length when it does not occur in the pattern at all.

	var shift [256]int
	for c := range shift {
		shift[c] = m
	}
	for j := 0; j < m-1; j++ {
		shift[pat[j]] = m - 1 - j
	}
	for i := 0; i+m <= len(text); {
		j := m - 1
		for j >= 0 {
			*cmps++
			if text[i+j] != pat[j] {
				break
			}
			j--
		}
		if j < 0 {
			res = append(res, i)
		}
		i += shift[text[i+m-1]]
	}

On ordinary text most windows end with a letter that is not in the pattern, so the window jumps by m. The result can be fewer than n comparisons, but the worst case is still O(n × m).

What the Demo Measures

No method wins everywhere. On random text Horspool reads only 15% of the characters. On the fourth row it is the naive method that is nearly free (the first comparison fails at once) and Horspool that slides one place at a time. KMP is the only one that never exceeds about 2n. Its guarantee is the reason it is taught, and the reason it is used when input can be adversarial.

Borders Give Periods

A border of length b means the string repeats with a shift of n − b. If that shift divides n, the string is a block repeated n/(n − b) times:

	p := n - prefixFunction(s)[n-1]
	if n%p == 0 {
		return p
	}
	return n

The smallest period of abcabcabc is 3, of abcabca is 7 (the shift 3 does not divide 7, so the string is not a repetition), and of aaaa is 1. The demo compares this with trying every length on 3,000 strings, half of them built to be periodic. Failures: 0.

Hashing Strings

Comparing two strings costs O(length). If you can turn each string into a number in such a way that equal strings give equal numbers, comparisons become O(1). A polynomial hash reads the characters as digits of a number in base B, modulo a large M: hash(s) = s[0]·Bm-1 + ... + s[m-1] (mod M). Two properties make it useful, and one warning goes with it. The demo is 65_rolling_hash.go.

• Rolling. Sliding a window one character right costs O(1): subtract the leading character's term, multiply by B, add the new character.
• Prefix hashes. With the hash of every prefix stored, the hash of any substring is one subtraction and one multiplication.
• Warning. Different strings can have the same hash (a collision). A hash match is evidence, not proof.

Sliding the window one place: remove, shift, add.

Rabin-Karp

Hash the pattern, roll a window of the same length over the text, and compare hashes. Only when hashes are equal, compare the real characters. That verification makes the answer always exact; the hash only decides how often the expensive check runs.

		// roll: drop text[i], shift everything one place, add text[i+m]
		ht = ((ht+mod-uint64(text[i])*pw%mod)*base + uint64(text[i+m])) % mod

The demo counts false hits, hash matches where the text differed, for a random 100,000-letter text and a pattern of 8 letters that occurs once:

With modulus 101 about one window in a hundred collides, so verification runs 988 extra times, yet the result is still right on 3,000 random tests: a weak hash makes the algorithm slower, not wrong.

A Large Modulus Without Overflow

To use prefix hashes for comparison only, with no verification, the modulus must be so large that a collision among the millions of comparisons is practically impossible. A convenient choice is the Mersenne prime 2⁶¹ − 1. Multiplying two numbers below it needs 122 bits, but Go's math/bits.Mul64 returns the full product as two 64-bit halves, and because 2⁶¹ is congruent to 1 (mod 2⁶¹ − 1), the high part can simply be added to the low part:

func mulmod(a, b uint64) uint64 {
	hi, lo := bits.Mul64(a, b)
	r := (lo & mod) + (lo >> 61) + (hi << 3)
	r = (r & mod) + (r >> 61)
	if r >= mod {
		r -= mod
	}
	return r
}

The demo checks this against math/big on 100,000 random products, including the largest possible operands. Failures: 0. Choose the base at random when the program starts: a fixed, well-known base and modulus can be attacked by someone who builds two different strings with the same hash.

Substring Hash in O(1)

	for i := 0; i < len(s); i++ {
		h.pre[i+1] = addmod(mulmod(h.pre[i], base), uint64(s[i])+1)
		h.pow[i+1] = mulmod(h.pow[i], base)
	}

func (h *Hasher) Get(l, r int) uint64 {
	return submod(h.pre[r], mulmod(h.pre[l], h.pow[r-l]))
}

pre[r] is pre[l] shifted left by r-l places plus the hash of s[l:r], so subtracting the shifted copy leaves the substring's own hash. Note the +1 when a character is added: without it, a character with value 0 would be invisible. On a 2,000-character string over a two-letter alphabet, where many substrings are equal, the demo compares 200,000 random pairs of substrings by hash and by real comparison, 33,204 of which are equal, and they disagree 0 times.

Binary Search on the Length

"Is there a substring of length L that occurs twice?" is easy with hashes: hash every window, and look for two equal values. It is also monotone: if a substring of length L repeats, its prefix of length L − 1 repeats too. So the longest repeated substring can be found by binary search on L, with O(n) work per step:

	lo, hi, at := 0, len(s)-1, 0 // invariant: length lo works, length hi+1 does not
	for lo < hi {
		mid := (lo + hi + 1) / 2
		if i := repeated(mid); i >= 0 {
			lo, at = mid, i
		} else {
			hi = mid - 1
		}
	}
	return s[at : at+lo]

Each equal-hash pair is verified with a real comparison, so a collision cannot produce a wrong answer. The same search finds the longest common substring of two strings: hash the windows of one string and look for them in the other. For banana the answer is ana; for xabcdey and zabcdew it is abcde. Both are compared with a brute force and with an O(n × m) dynamic-programming table on 300 random pairs. Failures: 0. On a random 200,000-letter text over four letters the longest repeated substring has 16 letters.

Palindromes by Hash

A substring is a palindrome when it equals its own reverse, and the reverse of s[l:r] is the substring of reverse(s) at [n-r, n-l). With prefix hashes of both strings, the test is one comparison:

		if isPal != (fw.Get(l, r) == rv.Get(len(p)-r, len(p)-l)) {

That answers "is this range a palindrome?" in O(1) after O(n) preparation. To find palindromes without asking about every range, the next section has a better tool.

Palindromes and Manacher's Algorithm

A palindrome is defined by its center. A string of n characters has 2n − 1 centers: each character (palindromes of odd length) and each gap between two characters (even length). Every palindromic substring grows from exactly one of them, so three questions become one: how far can the palindrome around this center grow? The longest palindromic substring, the number of palindromic substrings, and the longest palindromic prefix all follow from the answers. The demo is 66_palindromes.go.

Expand Around Each Center

Store two arrays: d1[i], the number of odd palindromes centered on character i, and d2[i], the number of even palindromes centered on the gap before character i. A center with radius k owns exactly k palindromes, one of each length up to the longest. For abaabac the arrays are:

d1 = [1 2 1 1 2 1 1]
d2 = [0 0 0 3 0 0 0]

The gap before index 3 (between the two middle as) has radius 3, so abaaba is a palindrome; there are 9 + 3 = 12 palindromic substrings in total, and longest picks the biggest radius. Growing every center from scratch costs O(n) per center in the worst case: O(n²), and it is the right choice up to a few thousand characters.

Manacher: Reuse the Mirror

Inside a large palindrome the left half is the mirror image of the right half. Suppose [l, r] is the palindrome that reaches furthest right among those found so far, and i is a center inside it. The mirror of i is l + r − i, and any palindrome around the mirror also exists around i, as long as it stays inside [l, r]. So the radius at i can start from the radius at the mirror (capped at the edge) instead of from 1.

	for i, l, r := 0, 0, -1; i < n; i++ {
		k := 1
		if i <= r {
			k = min(d1[l+r-i], r-i+1) // copy from the mirror, capped at the edge
		}
		for i-k >= 0 && i+k < n && s[i-k] == s[i+k] {
			cmps++
			k++
		}
		d1[i] = k
		if i+k-1 > r {
			l, r = i-k+1, i+k-1
		}
	}

The for loop that grows the palindrome only ever compares characters at or beyond the right edge r, and every successful comparison moves r to the right. Since r never moves left, the total number of successful comparisons is at most n: the algorithm is O(n). The even-length case (d2) is the same with the indexes shifted by one.

The cap r-i+1 matters: beyond the edge of the big palindrome nothing is known about the mirror, so the loop must check the characters itself.

What the Demo Measures

On random letters palindromes are short and there is nothing to reuse. On a run of identical letters, where every center has a huge palindrome, Manacher is 5,000 times cheaper. The results are checked two ways on 4,000 random strings over alphabets of size 1, 2 and 3: the two arrays against the slow expansion, and the answers (longest palindrome, count, shortest palindrome) against an O(n³) brute force. Failures: 0.

Application: Shortest Palindrome

What is the fewest characters to add in front of a string to make it a palindrome? The longest palindromic prefix can stay as it is; the remaining tail must be mirrored to the front. The prefixes that are palindromes are exactly the palindromes whose left edge is at index 0, which the arrays give directly:

	d1, d2 := manacher(s)
	p := longestPalPrefix(s, d1, d2)
	return reverse(s[p:]) + s

For aacecaaa the longest palindromic prefix is aacecaa and the answer is aaacecaaa; for abcd only a qualifies and the answer is dcbabcd.

Suffix Arrays

The tools so far answer one question about one pattern. Suppose instead a text will be queried many times, with different patterns, or you want to know about repetition inside it. Sort all the suffixes of the text once, and many questions become easy. The suffix array lists the start positions of the suffixes in dictionary order. The demo is 67_suffix_array.go.

The suffix array and LCP array of banana.

Two facts make the array powerful. Every substring is a prefix of some suffix, and suffixes that share a prefix are neighbours in sorted order. The LCP array stores, for each suffix, how many leading characters it shares with the suffix just before it in the sorted order; this is where repetition shows up.

Building It: Prefix Doubling

Sorting the suffix strings directly can cost O(n) per comparison. Prefix doubling sorts by the first character, then by the first two, then four, eight, and so on. In each round, the order by the first 2k characters is the order of pairs of ranks from the previous round: the rank of the suffix itself and the rank of the suffix k places later (or −1 if it runs out). After at most log₂ n rounds all ranks are distinct.

	for k := 1; ; k <<= 1 {
		rounds++
		second := func(i int) int {
			if i+k < n {
				return rank[i+k]
			}
			return -1
		}
		compare := func(a, b int) int {
			if c := cmp.Compare(rank[a], rank[b]); c != 0 {
				return c
			}
			return cmp.Compare(second(a), second(b))
		}
		slices.SortFunc(sa, compare)
		next[sa[0]] = 0
		for i := 1; i < n; i++ {
			next[sa[i]] = next[sa[i-1]]
			if compare(sa[i-1], sa[i]) != 0 {
				next[sa[i]]++
			}
		}
		copy(rank, next)
		if rank[sa[n-1]] == n-1 { // all ranks distinct: fully sorted
			return sa
		}
	}

Each round is one sort with O(1) comparisons, so the total is O(n log² n). The number of rounds depends on the text: random four-letter text of 30,000 characters is fully sorted after 4 rounds, because the first few letters already differ; a string of one repeated letter, or ab repeated, needs 15, which is log₂ n rounded up. Linear-time constructions exist but are much longer to write.

The LCP Array in O(n)

Comparing each suffix with its neighbour from scratch would cost O(n²) on repetitive text. Kasai's algorithm visits the suffixes in text order, not sorted order, and relies on one fact: if suffix i shares h characters with its predecessor in sorted order, then suffix i + 1 shares at least h − 1 with its own predecessor. So h never restarts; it falls by one per step and rises at most 2n times in total.

	for i := 0; i < n; i++ {
		if rank[i] == 0 {
			h = 0
			continue
		}
		j := sa[rank[i]-1] // the suffix just before i in sorted order
		for i+h < n && j+h < n && s[i+h] == s[j+h] {
			h++
		}
		lcp[rank[i]] = h
		if h > 0 {
			h--
		}
	}

What You Can Ask

Find a pattern. The suffixes that begin with the pattern form one contiguous block of the sorted array. Two binary searches find its ends: the first suffix that is not smaller than the pattern, and the first that is not smaller and does not start with it. The positions of the pattern are the array values in that block: O(m log n) per query, whatever the number of patterns you ask about.

	lo := sort.Search(len(sa), func(i int) bool { return s[sa[i]:] >= pat })
	hi := sort.Search(len(sa), func(i int) bool {
		suffix := s[sa[i]:]
		return suffix >= pat && !strings.HasPrefix(suffix, pat)
	})

In banana, ana occurs at [1 3], na at [2 4], and x nowhere.

Longest repeated substring. Two suffixes with a long common prefix are neighbours, so it is the largest LCP value: 3 for banana, the substring ana.

Number of distinct substrings. There are n(n+1)/2 pairs (start, end), and each suffix repeats as many prefixes as its LCP value: subtract them. For banana, 21 − (0+1+3+0+0+2) = 15.

	total := n * (n + 1) / 2
	for _, l := range lcp {
		total -= l
	}
	return total

Longest common substring of two strings. Build one array for a + separator + b. A common substring is a shared prefix of a suffix from a and one from b, so look at neighbouring pairs that come from different strings and take the largest LCP. The separator occurs once, so no LCP can run across it. For xabcdey and zabcdew the answer is abcde.

The demo checks the array and the LCP array against sorting the suffix strings, and every answer above against brute force (all substrings in a set, a DP table for the common substring) on 3,000 random strings over alphabets of size 1, 2 and 3. Failures: 0.

Many Patterns: Aho-Corasick

KMP finds one pattern in O(n + m). With k patterns, running it k times costs O(k × n): 500 patterns in a 200,000-letter text means 100,000,000 steps. The Aho-Corasick automaton finds all patterns in a single pass, and it is built from two things you already know: the trie (Advanced Trees) and the KMP fall-back. The demo is 68_aho_corasick.go.

The trie of four patterns, with each state's fail link.

Fail Links

Each node of the trie gets a fail link: the state for the longest proper suffix of the node's string that is also a prefix of some pattern. It is the border of KMP, generalized from one pattern to a whole trie. If the search is in the state for she and the next character does not continue any pattern, the automaton does not restart: it falls back to the state for he, the longest suffix of she that could still lead to a match, and tries again.

The links are computed level by level, breadth-first, so a node's fail link always points to a state that is already finished. Missing transitions are filled with the transition of the fail state. The result is a full automaton: the scan does exactly one table lookup per text character and never loops.

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		for c := 0; c < 26; c++ {
			v := a.next[u][c]
			if v == 0 {
				a.next[u][c] = a.next[a.fail[u]][c] // no child: borrow the fail state's move
				continue
			}
			a.fail[v] = a.next[a.fail[u]][c] // the longest suffix that can still be extended by c
			if len(a.ends[a.fail[v]]) > 0 {
				a.out[v] = a.fail[v]
			} else {
				a.out[v] = a.out[a.fail[v]]
			}
			queue = append(queue, v)
		}
	}

Output Links: Nested Patterns

Patterns can be suffixes of each other: he is a suffix of she, so when the text reads she, two patterns end at the same character. The output link of a state points along its fail chain to the nearest state that ends a pattern, so the search reports every match without walking through states that report nothing:

		*steps++
		s = a.next[s][c-'a']
		t := s // report the patterns ending here, then those ending in shorter suffixes
		if len(a.ends[t]) == 0 {
			t = a.out[t]
		}
		for ; t != 0; t = a.out[t] {
			for _, id := range a.ends[t] {
				res = append(res, Match{i, id})
			}
		}

In the demo, the text ushers gives she at 1..3, he at 2..3 and hers at 2..5 from four patterns and 10 states. A practical use is censoring: with the patterns bad and dad, the text this is a bad example of badge and dad becomes this is a *** example of ***ge and ***. Note that badge is also affected, because this is substring matching: a real filter also needs word boundaries.

What the Demo Measures

• Correctness. On 4,000 random inputs with patterns that may be empty, repeated, or nested inside each other, the sorted list of matches equals the one produced by calling strings.Index for each pattern. Failures: 0.
• One pass. 500 random patterns of 4 letters in 200,000 letters of text use an automaton of 1,378 states and 218 matches. It makes 200,000 table lookups, where one scan per pattern would need at least 100,000,000.
• Output size. The patterns a, aa, ..., a30 in a text of 1,000 letters a produce 29,565 matches from just 1,000 lookups; the matches themselves are the output, and their number can exceed the text length. The list equals the one from strings.Index.

Choosing an Algorithm

By Situation

When Simple Is Enough

The naive search is O(n × m) only in unlucky cases, and for a pattern of a few characters in a short text it is the fastest of all: no tables to build. Reach for the algorithms above when the input is large, when it can be adversarial, or when the same text is examined again and again. A good habit, used in every demo of this lesson, is to keep the simple version and use it as the oracle in your tests.

Common Pitfalls

Bytes, Runes, and Positions

Indexes returned by these algorithms are byte positions. For text with multi-byte characters, a byte position may fall inside a character, and a palindrome check on bytes can accept a sequence that is not valid text. Convert to []rune first when the input is not ASCII. The Aho-Corasick demo accepts only lowercase a-z and resets the automaton on any other byte; a table indexed by a byte would otherwise panic.

Trusting a Hash

A hash match is not a proof. Either verify the characters (Rabin-Karp, the repeated-substring search), or use a modulus so large, and a base so unpredictable, that a collision among all the comparisons you make is not a realistic concern. With a small modulus and no verification the results are simply wrong, as the lab shows. Do not use a hash with a known fixed base and modulus on input controlled by someone else.

The Separator

Gluing strings with a separator (pattern + "\x00" + text, or two strings for a suffix array) works only if the separator occurs in neither string. If it does, matches can span the seam, or the wrong string is credited with a suffix.

Overlapping Matches and Empty Patterns

Decide up front whether matches may overlap (aba in abababa occurs at 0, 2 and 4) and what an empty pattern means. After a full match KMP falls back to the border and continues; restarting from zero would silently lose overlapping matches. The demos define an empty pattern to have no occurrences.

Building Strings in a Loop

Since strings are immutable, s += x in a loop copies the whole string each time: O(n²) for n appends. Use strings.Builder, or fill a []byte, as the demos do. And remember that s[i:j] is cheap because it shares memory, but that also keeps the whole original string alive.

Half-Open Ranges

Most bugs in these algorithms are off-by-one errors in ranges. The demos use half-open ranges [l, r) for substrings and prefix hashes (as Go slices do) and closed indexes for an end position of a match; write down which one each variable uses before coding.

Practice Lab

Each exercise breaks one detail. Predict what will fail, run the demo, and explain why that check catches it.

Run the Demos

1. In 64_pattern_matching.go, in kmp, replace k = pi[k-1] after a full match by k = 0. Which matches are lost, and which row of the comparison table reports a mismatch?
2. In 65_rolling_hash.go, in rabinKarp, replace the check text[i:i+m] == pat by true. Compare the number of matches reported for each modulus with the correct answer of 1.
3. In 66_palindromes.go, remove the cap in k = min(d1[l+r-i], r-i+1), leaving only d1[l+r-i]. Why does the answer become wrong only for some strings?
4. In 67_suffix_array.go, delete the if h > 0 { h-- } step in lcpArray. The program panics. Follow the value of h to see why.
5. In 68_aho_corasick.go, delete the if ... else block that sets a.out[v]. The ushers example still prints results. Which of the checks fails, and what does the nested-pattern example print instead of 29,565?

Exercises

1. Rotation. Decide whether string B is a rotation of string A by searching for B in A + A. Why is that enough, and what length check is also needed?
2. Prefix occurrences. Using only the prefix function, count how many times each prefix of a string occurs in the string. Hint: every border is also an occurrence of a shorter prefix.
3. Repeated DNA. Find every 10-letter sequence that occurs more than once in a long DNA string, with a rolling hash. Compare against a map of substrings, in time and memory.
4. Fewest palindromes. The DP in Dynamic Programming cuts a string into the fewest palindromes. Replace its O(n²) palindrome table with the arrays from Manacher and check that the answers agree.
5. K-th distinct substring. Use the suffix array and the LCP array to print the k-th smallest distinct substring in dictionary order, without listing them all.
6. Word filter. Extend the censor example so that only whole words are censored. Which information does the automaton need to give you, and where is the check done?

Continue with Advanced Techniques.