search_test.go

     1  // Copyright 2012 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package strings_test
     6  
     7  import (
     8  	"slices"
     9  	. "strings"
    10  	"testing"
    11  )
    12  
    13  func TestFinderNext(t *testing.T) {
    14  	testCases := []struct {
    15  		pat, text string
    16  		index     int
    17  	}{
    18  		{"", "", 0},
    19  		{"", "abc", 0},
    20  		{"abc", "", -1},
    21  		{"abc", "abc", 0},
    22  		{"d", "abcdefg", 3},
    23  		{"nan", "banana", 2},
    24  		{"pan", "anpanman", 2},
    25  		{"nnaaman", "anpanmanam", -1},
    26  		{"abcd", "abc", -1},
    27  		{"abcd", "bcd", -1},
    28  		{"bcd", "abcd", 1},
    29  		{"abc", "acca", -1},
    30  		{"aa", "aaa", 0},
    31  		{"baa", "aaaaa", -1},
    32  		{"at that", "which finally halts.  at that point", 22},
    33  	}
    34  
    35  	for _, tc := range testCases {
    36  		got := StringFind(tc.pat, tc.text)
    37  		want := tc.index
    38  		if got != want {
    39  			t.Errorf("stringFind(%q, %q) got %d, want %d\n", tc.pat, tc.text, got, want)
    40  		}
    41  	}
    42  }
    43  
    44  func TestFinderCreation(t *testing.T) {
    45  	testCases := []struct {
    46  		pattern string
    47  		bad     [256]int
    48  		suf     []int
    49  	}{
    50  		{
    51  			"abc",
    52  			[256]int{'a': 2, 'b': 1, 'c': 3},
    53  			[]int{5, 4, 1},
    54  		},
    55  		{
    56  			"mississi",
    57  			[256]int{'i': 3, 'm': 7, 's': 1},
    58  			[]int{15, 14, 13, 7, 11, 10, 7, 1},
    59  		},
    60  		// From https://www.cs.utexas.edu/~moore/publications/fstrpos.pdf
    61  		{
    62  			"abcxxxabc",
    63  			[256]int{'a': 2, 'b': 1, 'c': 6, 'x': 3},
    64  			[]int{14, 13, 12, 11, 10, 9, 11, 10, 1},
    65  		},
    66  		{
    67  			"abyxcdeyx",
    68  			[256]int{'a': 8, 'b': 7, 'c': 4, 'd': 3, 'e': 2, 'y': 1, 'x': 5},
    69  			[]int{17, 16, 15, 14, 13, 12, 7, 10, 1},
    70  		},
    71  	}
    72  
    73  	for _, tc := range testCases {
    74  		bad, good := DumpTables(tc.pattern)
    75  
    76  		for i, got := range bad {
    77  			want := tc.bad[i]
    78  			if want == 0 {
    79  				want = len(tc.pattern)
    80  			}
    81  			if got != want {
    82  				t.Errorf("boyerMoore(%q) bad['%c']: got %d want %d", tc.pattern, i, got, want)
    83  			}
    84  		}
    85  
    86  		if !slices.Equal(good, tc.suf) {
    87  			t.Errorf("boyerMoore(%q) got %v want %v", tc.pattern, good, tc.suf)
    88  		}
    89  	}
    90  }
    91
View as plain text