kmp_test.gno

  1package kmp
  2
  3import (
  4	"strings"
  5	"testing"
  6
  7	"gno.land/p/nt/uassert/v0"
  8)
  9
 10func TestTable(t *testing.T) {
 11	cases := []struct {
 12		pattern string
 13		want    []int
 14	}{
 15		{"abcabca", []int{0, 0, 0, 1, 2, 3, 4}},
 16		{"aaaa", []int{0, 1, 2, 3}},
 17		{"abcd", []int{0, 0, 0, 0}},
 18		{"ababaa", []int{0, 0, 1, 2, 3, 1}},
 19		{"a", []int{0}},
 20	}
 21	for _, c := range cases {
 22		got := Table(c.pattern)
 23		uassert.Equal(t, len(c.want), len(got), "table length for "+c.pattern)
 24		for i := range c.want {
 25			uassert.Equal(t, c.want[i], got[i], "table["+itoa(i)+"] for "+c.pattern)
 26		}
 27	}
 28}
 29
 30func TestTableRejects(t *testing.T) {
 31	uassert.True(t, Table("") == nil, "empty pattern has no table")
 32	uassert.True(t, Table(strings.Repeat("x", MaxPattern+1)) == nil, "oversized pattern refused")
 33	uassert.False(t, Table(strings.Repeat("x", MaxPattern)) == nil, "exactly MaxPattern is allowed")
 34}
 35
 36// TestIndexMatchesStdlib pins KMP against strings.Index across a spread of
 37// inputs — same contract, different algorithm.
 38func TestIndexMatchesStdlib(t *testing.T) {
 39	texts := []string{"", "a", "hello world", "aaaaaaab", "abcabcabd", "mississippi"}
 40	pats := []string{"", "a", "b", "ab", "abd", "issi", "world", "zzz", "mississippi"}
 41	for _, text := range texts {
 42		for _, p := range pats {
 43			uassert.Equal(t, strings.Index(text, p), Index(text, p),
 44				"Index("+text+","+p+") should match strings.Index")
 45		}
 46	}
 47}
 48
 49func TestContains(t *testing.T) {
 50	uassert.True(t, Contains("hello world", "lo w"))
 51	uassert.False(t, Contains("hello world", "lo  w"))
 52	uassert.True(t, Contains("anything", ""), "empty pattern is always contained")
 53}
 54
 55// TestFindAllOverlapping is the documented divergence from a naive scan.
 56func TestFindAllOverlapping(t *testing.T) {
 57	got := FindAll("aaaa", "aa")
 58	uassert.Equal(t, 3, len(got), "overlapping matches are all reported")
 59	uassert.Equal(t, 0, got[0])
 60	uassert.Equal(t, 1, got[1])
 61	uassert.Equal(t, 2, got[2])
 62}
 63
 64func TestFindAllDisjoint(t *testing.T) {
 65	got := FindAll("abcabcabc", "abc")
 66	uassert.Equal(t, 3, len(got))
 67	uassert.Equal(t, 0, got[0])
 68	uassert.Equal(t, 3, got[1])
 69	uassert.Equal(t, 6, got[2])
 70}
 71
 72func TestFindAllAbsent(t *testing.T) {
 73	uassert.Equal(t, 0, len(FindAll("abc", "xyz")))
 74	uassert.Equal(t, 0, len(FindAll("ab", "abcdef")), "pattern longer than text")
 75}
 76
 77func TestCount(t *testing.T) {
 78	uassert.Equal(t, 4, Count("aaaaa", "aa"))
 79	uassert.Equal(t, 2, Count("mississippi", "issi"))
 80	uassert.Equal(t, 0, Count("abc", "d"))
 81}
 82
 83// TestPathologicalInput is the reason to use KMP: the naive scan is quadratic
 84// here, KMP is linear. Correctness is what we assert; the cost is the point.
 85func TestPathologicalInput(t *testing.T) {
 86	text := strings.Repeat("a", 2000) + "b"
 87	pattern := strings.Repeat("a", 200) + "b"
 88	uassert.Equal(t, 1800, Index(text, pattern))
 89	uassert.Equal(t, 1, Count(text, pattern))
 90}
 91
 92// TestBytesNotRunes documents that offsets are byte offsets.
 93func TestBytesNotRunes(t *testing.T) {
 94	// "é" is two bytes in UTF-8, so "x" sits at byte 2, not rune 1.
 95	uassert.Equal(t, 2, Index("éx", "x"))
 96	uassert.Equal(t, strings.Index("éx", "x"), Index("éx", "x"))
 97}
 98
 99func TestMatchAtStartAndEnd(t *testing.T) {
100	uassert.Equal(t, 0, Index("abcdef", "abc"))
101	uassert.Equal(t, 3, Index("abcdef", "def"))
102	uassert.Equal(t, 0, Index("abc", "abc"), "whole-string match")
103}
104
105func itoa(i int) string {
106	if i == 0 {
107		return "0"
108	}
109	s := ""
110	for i > 0 {
111		s = string(rune('0'+i%10)) + s
112		i /= 10
113	}
114	return s
115}