Go Guide

Core patterns · Lesson 25 of 62 · about 55 min

String algorithms

Build strings efficiently, find palindromes by expanding around centers, and search text in linear time with KMP's failure table and Rabin-Karp's rolling hash.

pkg.go.dev: strings ↗Go blog: Strings, bytes, runes and characters ↗
On this page · 9 sections
  1. 01Building strings efficiently
  2. 02Palindromes: expand around centers
  3. 03Pattern search: why the naive way is slow
  4. 04KMP: a table of what you already know
  5. 05Rabin-Karp: compare hashes, not strings
  6. 06Complexity
  7. 07Summary
  8. 08Check your understanding
  9. 09Practice in Go

Building strings efficiently#

Go strings are immutable byte sequences (lesson 2). s += x therefore creates a brand-new string and copies everything so far. In a loop that is O(n²). strings.Builder keeps a growing byte buffer, like append, and produces the final string once:

builder.go
Go
package main
 
import (
	"fmt"
	"strings"
)
 
func main() {
	var b strings.Builder
	b.Grow(64) // optional: reserve space when you know roughly how much you need
	for i := range 5 {
		fmt.Fprintf(&b, "%d,", i) // Builder is an io.Writer
	}
	b.WriteString("done")
	fmt.Println(b.String(), b.Len())
 
	// Common one-liners that avoid manual loops.
	words := strings.Fields("  the quick  brown fox ")
	fmt.Printf("%q\n", words)
	fmt.Println(strings.Join(words, "-"))
	fmt.Println(strings.Repeat("ab", 3), strings.ToUpper("go"), strings.TrimSpace("  x  "))
	fmt.Println(strings.Count("cheese", "e"), strings.Index("chicken", "ken"), strings.Contains("seafood", "foo"))
	fmt.Println(strings.Replace("oink oink oink", "k", "ky", 2), strings.Split("a,b,c", ","))
 
	// Reverse by runes, so multi-byte characters survive.
	r := []rune("héllo, 世界")
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	fmt.Println(string(r))
}
Output
0,1,2,3,4,done 14
["the" "quick" "brown" "fox"]
the-quick-brown-fox
ababab GO x
3 4 true
oinky oinky oink [a b c]
界世 ,olléh

Palindromes: expand around centers#

A palindrome mirrors around its center. The center is either a character (odd length, "racecar") or the gap between two characters (even length, "abba"). For each of the 2n - 1 centers, expand outward while the two ends match. Each expansion is O(n), so the total is O(n²) with O(1) memory, which is simple and fast enough for n up to a few thousand.

palindromes.go
Go
package main
 
import "fmt"
 
// expand grows from s[l..r] outward while the ends match and returns the widest palindrome bounds.
func expand(s string, l, r int) (int, int) {
	for l >= 0 && r < len(s) && s[l] == s[r] {
		l--
		r++
	}
	return l + 1, r // s[l+1:r] is the palindrome
}
 
func longestPalindrome(s string) string {
	best := s[:0]
	for i := range len(s) {
		for _, gap := range []int{0, 1} { // odd center at i, even center between i and i+1
			l, r := expand(s, i, i+gap)
			if r-l > len(best) {
				best = s[l:r]
			}
		}
	}
	return best
}
 
func countPalindromes(s string) int {
	count := 0
	for c := 0; c < 2*len(s)-1; c++ {
		l, r := c/2, c/2+c%2
		for l >= 0 && r < len(s) && s[l] == s[r] {
			count++ // every successful step is one more palindrome
			l--
			r++
		}
	}
	return count
}
 
func main() {
	for _, s := range []string{"babad", "cbbd", "forgeeksskeegfor", "a"} {
		fmt.Printf("%-18q longest=%q\n", s, longestPalindrome(s))
	}
	fmt.Println("palindromic substrings in \"aaa\":", countPalindromes("aaa"))
}
Output
"babad"            longest="bab"
"cbbd"             longest="bb"
"forgeeksskeegfor" longest="geeksskeeg"
"a"                longest="a"
palindromic substrings in "aaa": 6

"aaa" has 6: three a, two aa, and aaa. (Manacher's algorithm finds the longest palindrome in O(n) by reusing mirror information, but expand-around-center is what you should reach for first.)

Pattern search: why the naive way is slow#

"Find pattern in text." The naive approach tries every starting position and compares character by character. On text aaaa…ab and pattern aaab, nearly every attempt matches several characters before failing, so the work is O(n·m). The waste: after matching aaa and failing on b, we already know the next text characters are aa, yet the naive loop reads them again.

KMP: a table of what you already know#

Knuth-Morris-Pratt precomputes, for the pattern alone, an array lps ("longest proper prefix that is also a suffix"). lps[i] answers: "if I have matched p[:i+1] and then fail, how many characters at the start of the pattern are still matched?" The search then continues from there, and the text pointer never moves backward.

For the pattern ababc:

ip[:i+1]longest proper prefix = suffixlps[i]
0a(none)0
1ab(none)0
2abaa1
3ababab2
4ababc(none)0

Step through the table build and the search. Watch the moment of the first mismatch: the pattern slides, but i in the text stays where it is.

kmp.go
Go
package main
 
import (
	"fmt"
	"strings"
)
 
func buildLPS(p string) []int {
	lps := make([]int, len(p))
	for i, length := 1, 0; i < len(p); {
		switch {
		case p[i] == p[length]:
			length++
			lps[i] = length
			i++
		case length > 0:
			length = lps[length-1] // fall back to a shorter border; i stays
		default:
			lps[i] = 0
			i++
		}
	}
	return lps
}
 
// searchAll returns every index where p occurs in text, overlaps included. O(n + m).
func searchAll(text, p string) []int {
	lps := buildLPS(p)
	var out []int
	for i, j := 0, 0; i < len(text); {
		switch {
		case text[i] == p[j]:
			i++
			j++
			if j == len(p) {
				out = append(out, i-j)
				j = lps[j-1]
			}
		case j > 0:
			j = lps[j-1]
		default:
			i++
		}
	}
	return out
}
 
func main() {
	fmt.Println(buildLPS("ababc"), buildLPS("aabaaab"), buildLPS("abcabcabc"))
	fmt.Println(searchAll("abababcabab", "ababc"))
	fmt.Println(searchAll("aaaaa", "aa")) // overlapping matches
	fmt.Println(strings.Index("abababcabab", "ababc"))
 
	// A border trick: s is made of a repeated block if n is divisible by n - lps[n-1].
	for _, s := range []string{"abcabcabc", "abcab"} {
		lps := buildLPS(s)
		n, b := len(s), lps[len(s)-1]
		fmt.Printf("%s repeated block? %v\n", s, b > 0 && n%(n-b) == 0)
	}
}
Output
[0 0 1 2 0] [0 1 0 1 2 2 3] [0 0 0 1 2 3 4 5 6]
[2]
[0 1 2 3]
2
abcabcabc repeated block? true
abcab repeated block? false

Rabin-Karp: compare hashes, not strings#

Rabin-Karp turns each length-m window of the text into a number (a hash) and compares it to the pattern's hash. Only when the hashes match does it compare characters, to rule out a collision. The key is the rolling update: treat the window as a number in base B, so sliding right by one character is:

hash = (hash - text[i-m] * B^(m-1)) * B + text[i]      (all modulo a prime)

Remove the leaving character's contribution, shift everything one place, add the new character: O(1) per step, O(n + m) on average.

rabinkarp.go
Go
package main
 
import "fmt"
 
const (
	base = 256
	mod  = 1_000_000_007
)
 
func rabinKarp(text, p string) (matches []int, hashHits int) {
	n, m := len(text), len(p)
	if m > n {
		return nil, 0
	}
	pow := 1 // base^(m-1) % mod: the weight of the leftmost character
	for range m - 1 {
		pow = pow * base % mod
	}
	hp, ht := 0, 0
	for i := range m {
		hp = (hp*base + int(p[i])) % mod
		ht = (ht*base + int(text[i])) % mod
	}
	for i := 0; ; i++ {
		if ht == hp {
			hashHits++
			if text[i:i+m] == p { // confirm: hashes can collide
				matches = append(matches, i)
			}
		}
		if i+m == n {
			return matches, hashHits
		}
		ht = (ht - int(text[i])*pow%mod + mod) % mod // drop the leaving character
		ht = (ht*base + int(text[i+m])) % mod        // shift and add the entering one
	}
}
 
func main() {
	fmt.Println(rabinKarp("the cat sat on the mat with the hat", "the"))
	fmt.Println(rabinKarp("aaaaaaaa", "aaa"))
	fmt.Println(rabinKarp("gopher", "rust"))
}
Output
[0 15 28] 3
[0 1 2 3 4 5] 6
[] 0

The rolling hash shines when you need to compare many substrings, not just search for one pattern: "longest duplicated substring" binary searches on the length and, for each length, puts every window's hash into a set. Detecting plagiarism between documents uses the same trick.

Complexity#

AlgorithmTimeSpace
strings.Builder, n appendsO(total length)O(total length)
longest palindrome, expand around centerO(n²)O(1)
naive searchO(n · m) worst caseO(1)
KMPO(n + m) worst caseO(m)
Rabin-KarpO(n + m) average, O(n · m) with many collisionsO(1)

Summary#

  • Build strings with strings.Builder, never += in a loop.
  • Palindromes: expand around all 2n - 1 centers.
  • KMP's lps table records how much of the pattern still matches after a failure, so the text is read once.
  • Rabin-Karp compares rolling hashes and confirms matches; it generalizes to comparing many substrings.
  • Handle negative remainders when you subtract under a modulus.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.Why is s += piece inside a loop slow for building a long string?

  2. Q2.Expanding around centers finds the longest palindrome in O(n²). How many centers are there in a string of length n?

  3. Q3.In KMP, lps[i] is:

  4. Q4.Why does Rabin-Karp compare the actual substrings when the hashes match?

  5. Q5.What does the rolling hash do when the window slides one character to the right?

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.