Go语言中利用suffixarray实现多字符串自动补全及模式匹配

words := []string{
    "aardvark",
    "happy",
    "hello",
    "hero",
    "he",
    "hotel",
}

import (
    "index/suffixarray"
    "strings"
)

// 使用 \x00 作为分隔符，确保它不会出现在实际的字符串中。
// 在每个字符串前都添加分隔符，以便于正则匹配时区分每个词的开始。
joinedStrings := "\x00" + strings.Join(words, "\x00")
sa := suffixarray.New([]byte(joinedStrings))

import "regexp"

// 假设用户输入了 "he"
// 构建正则表达式：
// \x00 表示匹配字符串的起始分隔符
// regexp.QuoteMeta("he") 确保 "he" 中的特殊字符（如果有）被转义
// [^\x00]* 表示匹配任意非 \x00 的字符零次或多次，直到遇到下一个分隔符或字符串结束
query := "he"
matchPattern := regexp.QuoteMeta("\x00"+query) + "[^\x00]*"
match, err := regexp.Compile(matchPattern)
if err != nil {
    panic(err) // 处理正则表达式编译错误
}

import "fmt"

ms := sa.FindAllIndex(match, -1) // -1 表示查找所有匹配项

fmt.Printf("用户输入 '%s' 的自动补全结果:\n", query)
for _, m := range ms {
    start, end := m[0], m[1]
    // 匹配结果包含了起始的 \x00，因此需要从 start+1 开始截取，以获取原始单词
    fmt.Printf("- %q\n", joinedStrings[start+1:end])
}

package main

import (
    "fmt"
    "index/suffixarray"
    "regexp"
    "strings"
)

func main() {
    words := []string{
        "aardvark",
        "happy",
        "hello",
        "hero",
        "he",
        "hotel",
    }

    // 1. 拼接字符串与构建后缀数组
    // 使用 \x00 作为分隔符，确保它不会出现在实际的字符串中。
    // 在每个字符串前都添加分隔符，以便于正则匹配时区分每个词的开始。
    joinedStrings := "\x00" + strings.Join(words, "\x00")
    sa := suffixarray.New([]byte(joinedStrings))

    // 2. 示例一：用户输入 "he" 的自动补全
    query1 := "he"
    // 构建正则表达式：
    // \x00 表示匹配字符串的起始分隔符
    // regexp.QuoteMeta(query1) 确保用户输入中的特殊字符（如果有）被转义
    // [^\x00]* 表示匹配任意非 \x00 的字符零次或多次，直到遇到下一个分隔符或字符串结束
    matchPattern1 := regexp.QuoteMeta("\x00"+query1) + "[^\x00]*"
    match1, err := regexp.Compile(matchPattern1)
    if err != nil {
        panic(err) // 处理正则表达式编译错误
    }

    // 执行查找并解析结果
    ms1 := sa.FindAllIndex(match1, -1) // -1 表示查找所有匹配项

    fmt.Printf("用户输入 '%s' 的自动补全结果:\n", query1)
    for _, m := range ms1 {
        start, end := m[0], m[1]
        // 匹配结果包含了起始的 \x00，因此需要从 start+1 开始截取，以获取原始单词
        fmt.Printf("- %q\n", joinedStrings[start+1:end])
    }

    fmt.Println("--------------------")

    // 3. 示例二：用户输入 "h" 的自动补全
    query2 := "h"
    matchPattern2 := regexp.QuoteMeta("\x00"+query2) + "[^\x00]*"
    match2, err := regexp.Compile(matchPattern2)
    if err != nil {
        panic(err)
    }

    ms2 := sa.FindAllIndex(match2, -1)

    fmt.Printf("用户输入 '%s' 的自动补全结果:\n", query2)
    for _, m := range ms2 {
        start, end := m[0], m[1]
        fmt.Printf("- %q\n", joinedStrings[start+1:end])
    }
}

用户输入 'he' 的自动补全结果:
- "hello"
- "hero"
- "he"
--------------------
用户输入 'h' 的自动补全结果:
- "happy"
- "hello"
- "hero"
- "he"
- "hotel"