func find(text, pattern string) int {
    n, m := len(text), len(pattern)
    for i := 0; i <= n-m; i++ {
        j := 0
        for j < m && text[i+j] == pattern[j] {
            j++
        }
        if j == m {
            return i
        }
    }
    return -1
}

// 方法1：strings.Index —— 標(biāo)準(zhǔn)庫最常用
// 短模式走樸素，長(zhǎng)模式自動(dòng)切到 Rabin-Karp（見 Go 源碼 strings/search.go）
func find1(text, pattern string) int {
    return strings.Index(text, pattern)
}

// 方法2：strings.Contains —— 只關(guān)心"是否存在"
// 等價(jià)于 Index(...) >= 0，語義更明確
func find2(text, pattern string) bool {
    return strings.Contains(text, pattern)
}

// 方法3：HasPrefix 滑動(dòng)窗口
// 不構(gòu)造子串、零分配
func find3(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m == 0 {
        return 0
    }
    for i := 0; i <= n-m; i++ {
        if strings.HasPrefix(text[i:], pattern) {
            return i
        }
    }
    return -1
}

// 方法4：regexp 正則——支持復(fù)雜模式、大小寫不敏感
// regexp.QuoteMeta 把字符串里的元字符轉(zhuǎn)義，防止把用戶輸入當(dāng)正則解析
func find4(text, pattern string) []int {
    re := regexp.MustCompile(regexp.QuoteMeta(pattern))
    locs := re.FindAllStringIndex(text, -1)
    result := make([]int, 0, len(locs))
    for _, loc := range locs {
        result = append(result, loc[0])
    }
    return result
}

// 方法5：bytes.Index —— []byte 流上的查找
// 處理網(wǎng)絡(luò)包、文件讀取緩沖區(qū)時(shí)，比 string(buf) 轉(zhuǎn)換零拷貝
func find5(buf, pattern []byte) int {
    return bytes.Index(buf, pattern)
}

// 方法6：雙循環(huán)樸素——最經(jīng)典的 Brute Force
// 已是 nativesearch/string_search.go 中的實(shí)現(xiàn)
func find6(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m == 0 {
        return 0
    }
    for i := 0; i <= n-m; i++ {
        j := 0
        for j < m && text[i+j] == pattern[j] {
            j++
        }
        if j == m {
            return i
        }
    }
    return -1
}

// 方法7：[]byte 數(shù)組版——對(duì) string 直接做字節(jié)索引就是這種效果
// Go 的 string 已經(jīng)是只讀 byte 數(shù)組，[]byte(text) 會(huì)觸發(fā)拷貝
// 對(duì) string 直接 text[i] 沒有邊界檢查開銷，與方法6性能一致
func find7(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m == 0 {
        return 0
    }
    for i := 0; i <= n-m; i++ {
        match := true
        for j := 0; j < m; j++ {
            if text[i+j] != pattern[j] {
                match = false
                break
            }
        }
        if match {
            return i
        }
    }
    return -1
}

// 方法8：rune 版本——按 Unicode 字符比較
// 處理中文、emoji 時(shí)必須用 rune 而非 byte
// 注意：rune 切片會(huì)消耗 O(n) 額外空間
func find8(text, pattern string) int {
    tr, pr := []rune(text), []rune(pattern)
    n, m := len(tr), len(pr)
    if m == 0 {
        return 0
    }
    for i := 0; i <= n-m; i++ {
        j := 0
        for j < m && tr[i+j] == pr[j] {
            j++
        }
        if j == m {
            // 注意：返回的是 rune 下標(biāo)，要算字節(jié)位置需要遍歷前綴
            return i
        }
    }
    return -1
}

// 方法9：反向樸素——從右往左對(duì)齊
// BM 算法的雛形：從模式串最右開始比，失敗時(shí)直接跳到下一對(duì)齊
func find9(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m == 0 {
        return 0
    }
    for i := n - m; i >= 0; i-- {
        j := m - 1
        for j >= 0 && text[i+j] == pattern[j] {
            j--
        }
        if j < 0 {
            return i
        }
    }
    return -1
}

// 方法10：KMP 算法——利用已匹配信息避免回溯
// 完整實(shí)現(xiàn)見 KMPsearch/kmp_search.go
// 核心：next[i] = pattern[0..i] 的最長(zhǎng)真前綴也是真后綴的長(zhǎng)度
func find10(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m == 0 {
        return 0
    }
    // 構(gòu)建 next 數(shù)組
    next := make([]int, m)
    k := 0
    for i := 1; i < m; i++ {
        for k > 0 && pattern[i] != pattern[k] {
            k = next[k-1]
        }
        if pattern[i] == pattern[k] {
            k++
        }
        next[i] = k
    }
    // 主串掃描，j 永不回退
    j := 0
    for i := 0; i < n; i++ {
        for j > 0 && text[i] != pattern[j] {
            j = next[j-1]
        }
        if text[i] == pattern[j] {
            j++
        }
        if j == m {
            return i - m + 1
        }
    }
    return -1
}

// 方法11：Boyer-Moore（壞字符規(guī)則）
// 從模式串右端開始比，失配按"該字符在模式中最右出現(xiàn)位置"跳躍
// 在自然文本中常常能跳過 m 位（接近線性時(shí)間）
func find11(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m == 0 {
        return 0
    }
    // 壞字符表：256 字節(jié)字符集
    var badChar [256]int
    for i := range badChar {
        badChar[i] = -1
    }
    for i := 0; i < m; i++ {
        badChar[pattern[i]] = i
    }
    shift := 0
    for shift <= n-m {
        j := m - 1
        for j >= 0 && pattern[j] == text[shift+j] {
            j--
        }
        if j < 0 {
            return shift
        }
        // max(1, ...) 防止跳到負(fù)數(shù)
        delta := j - badChar[text[shift+j]]
        if delta < 1 {
            delta = 1
        }
        shift += delta
    }
    return -1
}

// 方法12：Sunday 算法——BM 的簡(jiǎn)化變種
// 關(guān)鍵：失配時(shí)看"窗口右側(cè)外那一格"，它將來必然要參與對(duì)齊
// 在英文文本上常常比 BM 還快
func find12(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m == 0 {
        return 0
    }
    // shift[c] = 字符 c 在模式串中最右出現(xiàn)位置，讓其與新窗口對(duì)齊
    var shift [256]int
    for i := range shift {
        shift[i] = m + 1
    }
    for i := 0; i < m; i++ {
        shift[pattern[i]] = m - i
    }
    i := 0
    for i <= n-m {
        j := 0
        for j < m && text[i+j] == pattern[j] {
            j++
        }
        if j == m {
            return i
        }
        if i+m >= n {
            return -1
        }
        i += shift[text[i+m]]
    }
    return -1
}

// 方法13：Horspool 算法——BM 的另一種簡(jiǎn)化
// 失配時(shí)只看"主串對(duì)齊到模式串末尾的字符"，不計(jì)算 j-badChar[c]
// 代碼更短，性能在多數(shù)場(chǎng)景接近 BM
func find13(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m == 0 {
        return 0
    }
    var shift [256]int
    for i := range shift {
        shift[i] = m
    }
    for i := 0; i < m-1; i++ {
        shift[pattern[i]] = m - 1 - i
    }
    i := 0
    for i <= n-m {
        j := m - 1
        for j >= 0 && pattern[j] == text[i+j] {
            j--
        }
        if j < 0 {
            return i
        }
        i += shift[text[i+m-1]]
    }
    return -1
}

// 方法14：Rabin-Karp（滾動(dòng)哈希）
// 完整實(shí)現(xiàn)見 pattern-matching/ 中類比版本
// 核心：先比較窗口的哈希，相等再確認(rèn)（解決沖突）
// 多模式同時(shí)查找時(shí)極其有用——所有模式串預(yù)算哈希存 map，掃一遍主串
func find14(text, pattern string) int {
    n, m := len(text), len(pattern)
    if m == 0 {
        return 0
    }
    if m > n {
        return -1
    }
    const (
        D = 256
        Q = 1000000007 // 大素?cái)?shù)防沖突
    )
    h := uint64(1)
    for i := 0; i < m-1; i++ {
        h = (h * D) % Q
    }
    var p, t uint64
    for i := 0; i < m; i++ {
        p = (D*p + uint64(pattern[i])) % Q
        t = (D*t + uint64(text[i])) % Q
    }
    for i := 0; i <= n-m; i++ {
        if p == t {
            j := 0
            for j < m && text[i+j] == pattern[j] {
                j++
            }
            if j == m {
                return i
            }
        }
        if i < n-m {
            // Go 中 uint 減法是模運(yùn)算，不會(huì)成負(fù)，但 (t - text[i]*h) 可能溢出
            // 用 +Q 保正再取模
            t = (D*((t+Q-uint64(text[i])*h%Q)%Q) + uint64(text[i+m])) % Q
        }
    }
    return -1
}

// 方法15：Trie 前綴樹——多個(gè)模式串的前綴查詢
// 適合自動(dòng)補(bǔ)全、敏感詞字典查詢等場(chǎng)景
type Trie struct {
    children [26]*Trie // 僅小寫英文，工程里用 map[byte]*Trie
    isEnd    bool
}

func (t *Trie) Insert(word string) {
    cur := t
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if cur.children[idx] == nil {
            cur.children[idx] = &Trie{}
        }
        cur = cur.children[idx]
    }
    cur.isEnd = true
}

func (t *Trie) Contains(word string) bool {
    n := t.walk(word)
    return n != nil && n.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.walk(prefix) != nil
}

func (t *Trie) walk(s string) *Trie {
    cur := t
    for i := 0; i < len(s); i++ {
        cur = cur.children[s[i]-'a']
        if cur == nil {
            return nil
        }
    }
    return cur
}

// 方法16：AC 自動(dòng)機(jī)——Trie + 失敗指針
// 一次掃描主串，找出所有模式串的所有出現(xiàn)
// 是敏感詞過濾、入侵檢測(cè)的標(biāo)準(zhǔn)算法
type ACNode struct {
    children map[byte]*ACNode
    fail     *ACNode
    hits     []string // 該節(jié)點(diǎn)結(jié)尾的模式串
}

type AhoCorasick struct {
    root *ACNode
}

func NewAhoCorasick() *AhoCorasick {
    return &AhoCorasick{root: &ACNode{children: map[byte]*ACNode{}}}
}

func (ac *AhoCorasick) Add(p string) {
    cur := ac.root
    for i := 0; i < len(p); i++ {
        c := p[i]
        if cur.children[c] == nil {
            cur.children[c] = &ACNode{children: map[byte]*ACNode{}}
        }
        cur = cur.children[c]
    }
    cur.hits = append(cur.hits, p)
}

func (ac *AhoCorasick) Build() {
    queue := []*ACNode{}
    for _, child := range ac.root.children {
        child.fail = ac.root
        queue = append(queue, child)
    }
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        for c, v := range u.children {
            // v 的失敗指針：從 u.fail 沿 c 走
            f := u.fail
            for f != nil && f.children[c] == nil {
                f = f.fail
            }
            if f == nil {
                v.fail = ac.root
            } else {
                v.fail = f.children[c]
            }
            // 累加失敗鏈上的命中
            v.hits = append(v.hits, v.fail.hits...)
            queue = append(queue, v)
        }
    }
}

func (ac *AhoCorasick) Search(text string) [][2]int {
    var result [][2]int
    cur := ac.root
    for i := 0; i < len(text); i++ {
        c := text[i]
        for cur != ac.root && cur.children[c] == nil {
            cur = cur.fail
        }
        if next := cur.children[c]; next != nil {
            cur = next
        }
        for _, hit := range cur.hits {
            result = append(result, [2]int{i - len(hit) + 1, len(hit)})
        }
    }
    return result
}

// 方法17：后綴數(shù)組 + 二分查找
// 適合"主串固定、反復(fù)查不同模式"的場(chǎng)景
// 樸素構(gòu)建 O(n2 log n)，sort 接口帶來便利
type SuffixArray struct {
    text string
    sa   []int
}

func NewSuffixArray(text string) *SuffixArray {
    n := len(text)
    sa := make([]int, n)
    for i := range sa {
        sa[i] = i
    }
    // 樸素 O(n2 log n)；工程上用 SA-IS 實(shí)現(xiàn) O(n)
    sort.Slice(sa, func(i, j int) bool {
        return text[sa[i]:] < text[sa[j]:]
    })
    return &SuffixArray{text: text, sa: sa}
}

func (s *SuffixArray) Search(pattern string) int {
    lo, hi := 0, len(s.sa)-1
    for lo <= hi {
        mid := (lo + hi) / 2
        suf := s.text[s.sa[mid]:]
        if strings.HasPrefix(suf, pattern) {
            return s.sa[mid]
        }
        if suf < pattern {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

// 方法18：strings.Reader + 流式查找
// 不能一次讀進(jìn)內(nèi)存的大文件可以這么處理
func find18(reader *strings.Reader, pattern string) []int {
    // 簡(jiǎn)化：先全部讀出來。真實(shí)場(chǎng)景用 bufio.Reader 分塊 + 上下文保留
    data, _ := io.ReadAll(reader)
    var result []int
    text := string(data)
    for i := 0; ; {
        pos := strings.Index(text[i:], pattern)
        if pos < 0 {
            break
        }
        result = append(result, i+pos)
        i += pos + 1
    }
    return result
}

// 方法19：Z 算法——線性時(shí)間擴(kuò)展前綴
// Z[i] = 以 i 開頭的后綴與原串的最長(zhǎng)公共前綴長(zhǎng)度
// 拼接 "pattern + 分隔符 + text" 跑一遍 Z，所有 Z[i]==m 的位置就是匹配
func find19(text, pattern string) int {
    m := len(pattern)
    if m == 0 {
        return 0
    }
    s := pattern + "#" + text
    z := computeZ(s)
    for i := m + 1; i < len(s); i++ {
        if z[i] == m {
            return i - m - 1
        }
    }
    return -1
}

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

// 方法20：Bitap (Shift-And) ——位并行匹配
// 用 uint64 的每一位表示"模式串前綴 i 是否匹配到當(dāng)前位置"
// 一次位運(yùn)算推進(jìn)所有前綴，CPU 上極快
// 限制：模式串長(zhǎng)度 ≤ 64
// 真正威力：模糊匹配——k 個(gè) uint64 數(shù)組同時(shí)跟蹤 k 個(gè)錯(cuò)誤內(nèi)的所有匹配
func find20(text, pattern string) int {
    m := len(pattern)
    if m == 0 {
        return 0
    }
    if m > 63 {
        panic("Bitap 單 uint64 版只支持 m <= 63")
    }
    var mask [256]uint64
    for i := 0; i < m; i++ {
        mask[pattern[i]] |= 1 << i
    }
    var state uint64
    matchBit := uint64(1) << (m - 1)
    for i := 0; i < len(text); i++ {
        // 推進(jìn)所有前綴進(jìn)度，然后與當(dāng)前字符的 mask 相與
        state = ((state << 1) | 1) & mask[text[i]]
        if state&matchBit != 0 {
            return i - m + 1
        }
    }
    return -1
}

// 單次查找：標(biāo)準(zhǔn)庫已經(jīng)夠好
pos := strings.Index(text, pattern)

// 找全部位置
re := regexp.MustCompile(regexp.QuoteMeta(pattern))
locs := re.FindAllStringIndex(text, -1) // [[start1,end1], [start2,end2], ...]

// 標(biāo)準(zhǔn)庫已經(jīng)在長(zhǎng)模式上自動(dòng)切到 Rabin-Karp
// 一般不需要自己實(shí)現(xiàn) BM/Sunday
pos := strings.Index(text, longPattern)

// AC 自動(dòng)機(jī)
ac := NewAhoCorasick()
for _, p := range patterns {
    ac.Add(p)
}
ac.Build()
hits := ac.Search(text)

// 標(biāo)準(zhǔn)庫后綴數(shù)組
import "index/suffixarray"
sa := suffixarray.New([]byte(largeText))
positions := sa.Lookup([]byte(pattern), -1) // 返回全部出現(xiàn)位置

trie := &Trie{}
for _, w := range dictionary {
    trie.Insert(w)
}
exists := trie.Contains("apple")
prefix := trie.StartsWith("app")

// ? 反例：N 個(gè)模式 × M 次掃描 = O(N × M × n)
for _, p := range patterns {
    if strings.Contains(text, p) {
        hit(p)
    }
}

// 把多個(gè)模式拼成一個(gè) RE2 正則
// RE2 內(nèi)部會(huì)編譯為 NFA/DFA，效率取決于實(shí)現(xiàn)
parts := make([]string, len(patterns))
for i, p := range patterns {
    parts[i] = regexp.QuoteMeta(p)
}
re := regexp.MustCompile(strings.Join(parts, "|"))
locs := re.FindAllStringIndex(text, -1)

// 關(guān)鍵：跨緩沖區(qū)邊界的匹配會(huì)被切斷，需要保留 m-1 字符的"上下文"
func streamSearch(r io.Reader, pattern string) []int {
    m := len(pattern)
    buf := make([]byte, 0, 8192+m)
    chunk := make([]byte, 8192)
    var result []int
    var totalOffset int

    for {
        n, err := r.Read(chunk)
        if n > 0 {
            buf = append(buf, chunk[:n]...)
            // 在 buf 里找匹配
            offset := 0
            for {
                idx := bytes.Index(buf[offset:], []byte(pattern))
                if idx < 0 {
                    break
                }
                result = append(result, totalOffset+offset+idx)
                offset += idx + 1
            }
            // 保留末尾 m-1 字節(jié)，避免跨緩沖區(qū)漏匹配
            if len(buf) > m-1 {
                drop := len(buf) - (m - 1)
                totalOffset += drop
                buf = buf[drop:]
            }
        }
        if err != nil {
            break
        }
    }
    return result
}

text := "你好world"
fmt.Println(len(text))   // 11（"你"、"好"各 3 字節(jié)，"world" 5 字節(jié)）
fmt.Println(text[0])     // 228（第一個(gè)字節(jié)，不是字符 '你'）

// 方式1：轉(zhuǎn) []rune
runes := []rune(text)
fmt.Println(len(runes))  // 7

// 方式2：for ... range
for i, r := range text {
    fmt.Printf("byte %d: %c\n", i, r)
}

// 方式3：utf8 包
import "unicode/utf8"
fmt.Println(utf8.RuneCountInString(text)) // 7

// 簡(jiǎn)單粗暴：全部轉(zhuǎn)小寫
strings.Contains(strings.ToLower(text), strings.ToLower(pattern))

// 嚴(yán)格 Unicode 折疊（處理土耳其 i/I、德語 ? 等）
strings.EqualFold(s1, s2) // 僅適用于"全等"判斷

// 正則
re := regexp.MustCompile("(?i)" + regexp.QuoteMeta(pattern))

// 在 []T 中查找 []T 模式（T 必須可比較）
func IndexSeq[T comparable](haystack, needle []T) int {
    n, m := len(haystack), len(needle)
    if m == 0 {
        return 0
    }
    for i := 0; i <= n-m; i++ {
        j := 0
        for j < m && haystack[i+j] == needle[j] {
            j++
        }
        if j == m {
            return i
        }
    }
    return -1
}