{`.(.)`, "abcd", build(2, 0, 2, 1, 2, 2, 4, 3, 4)},
	{`ab*`, "abbaab", build(3, 0, 3, 3, 4, 4, 6)},
	{`a(b*)`, "abbaab", build(3, 0, 3, 1, 3, 3, 4, 4, 4, 4, 6, 5, 6)},

	// fixed bugs
	{`ab$`, "cab", build(1, 1, 3)},
	{`axxb$`, "axxcb", nil},
	{`data`, "daXY data", build(1, 5, 9)},
	{`da(.)a$`, "daXY data", build(1, 5, 9, 7, 8)},
	{`zx+`, "zzx", build(1, 1, 3)},
	{`ab$`, "abcab", build(1, 3, 5)},
	{`(aa)*$`, "a", build(1, 1, 1, -1, -1)},

E	SAME		aaaaaab		(0,6)(0,6)
E	([ab]*)*	a		(0,1)(0,1)
E	SAME		aaaaaa		(0,6)(0,6)
E	SAME		ababab		(0,6)(0,6)
E	SAME		bababa		(0,6)(0,6)
E	SAME		b		(0,1)(0,1)
E	SAME		bbbbbb		(0,6)(0,6)
E	SAME		aaaabcde	(0,5)(0,5)
E	([^a]*)*	b		(0,1)(0,1)
E	SAME		bbbbbb		(0,6)(0,6)
E	SAME		aaaaaa		(0,0)(0,0)
E	([^ab]*)*	ccccxx		(0,6)(0,6)
E	SAME		ababab		(0,0)(0,0)

E	((z)+|a)*	zabcde		(0,2)(1,2)

a
ahogy
ahol
aki
akik
akkor
alatt
által
általában
amely
amelyek
amelyekben
amelyeket
amelyet
amelynek
ami
amit
amolyan
amíg
amikor
át
abban
ahhoz
annak
arra
arról
az
azok
azon
azt
azzal
azért
aztán
azután
azonban
bár
be
belül
benne
cikk
cikkek
cikkeket
csak
de
e
eddig
egész
egy

		expectedIsLatest    bool
	}{
		{
			fis:            getNFInfo(16, 16, 1603863445, "36a21454-a2ca-11eb-bbaa-93a81c686f21", nil, nil),
			modTime:        time.Unix(1603863445, 0),
			expectedErr:    nil,
			expectedQuorum: 8,
		},
		{
			fis:            getNFInfo(16, 7, 1603863445, "36a21454-a2ca-11eb-bbaa-93a81c686f21", nil, nil),
			modTime:        time.Unix(1603863445, 0),
			expectedErr:    InsufficientReadQuorum{},

	{"foo:and:bar", "foo", -1, []string{"", ":and:bar"}},
	{"foo:and:bar", "bar", -1, []string{"foo:and:", ""}},
	{"foo:and:bar", "baz", -1, []string{"foo:and:bar"}},
	{"baabaab", "a", -1, []string{"b", "", "b", "", "b"}},
	{"baabaab", "a*", -1, []string{"b", "b", "b"}},
	{"baabaab", "ba*", -1, []string{"", "", "", ""}},
	{"foobar", "f*b*", -1, []string{"", "o", "o", "a", "r"}},
	{"foobar", "f+.*b+", -1, []string{"", "ar"}},

    }

    def "can find prefix match"() {
        def trie = Trie.from("aaa", "bbb")
        expect:
        !trie.find("a")
        !trie.find("aa")
        trie.find("aaaa")
        trie.find("aaab")
    }

		}
		return out
	})
}

// test tests an arbitrary suffix array construction function.
// Generates many inputs, builds and checks suffix arrays.
func test(t *testing.T, build func([]byte) []int) {
	t.Run("ababab...", func(t *testing.T) {
		// Very repetitive input has numLMS = len(x)/2-1
		// at top level, the largest it can be.
		// But maxID is only two (aba and ab$).
		size := 100000
		if testing.Short() {

quanta
quante
quello
quelli
quella
quelle
questo
questi
questa
queste
si
tutto
tutti
a
c
e
i
l
o
ho
hai
ha
abbiamo
avete
hanno
abbia
abbiate
abbiano
avrò
avrai
avrà
avremo
avrete
avranno
avrei
avresti
avrebbe
avremmo
avreste
avrebbero
avevo
avevi
aveva
avevamo
avevate
avevano

        "CAFEBABE"                         | ByteArrayBackedHashCode | 4      | 0xBEBAFECA | toBytes(0xCA, 0xFE, 0xBA, 0xBE)
        "abbaabba"                         | ByteArrayBackedHashCode | 4      | 0xBAABBAAB | toBytes([0xAB, 0xBA] * 2)
        "abbaabbaabba"                     | ByteArrayBackedHashCode | 6      | 0xBAABBAAB | toBytes([0xAB, 0xBA] * 3)

var trimTests = []struct {
	f            string
	in, arg, out string
}{
	{"Trim", "abba", "a", "bb"},
	{"Trim", "abba", "ab", ""},
	{"TrimLeft", "abba", "ab", ""},
	{"TrimRight", "abba", "ab", ""},
	{"TrimLeft", "abba", "a", "bba"},
	{"TrimLeft", "abba", "b", "abba"},
	{"TrimRight", "abba", "a", "abb"},
	{"TrimRight", "abba", "b", "abba"},
	{"Trim", "<tag>", "<>", "tag"},
	{"Trim", "* listitem", " *", "listitem"},