php tire树,golang刷leetcode 经典（10） tire树与ac自动机

Trie树和AC自动机是字符串匹配的两种经典算法。Trie树是一种树形结构，用于存储一组字符串，常用于字符串查找、前缀匹配等场景。AC自动机是对Trie树的改进，可以在多个模式串中进行高效的匹配。

PHP的Trie树实现比较简单，可以用数组来模拟树的结构。例如，下面是一个实现前缀匹配的Trie树的示例代码：

class TrieNode {
    public $children = [];
    public $isEndOfWord = false;
}

class Trie {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    public function insert(string $word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
        }
        $node->isEndOfWord = true;
    }

    public function search(string $word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return $node->isEndOfWord;
    }

    public function startsWith(string $prefix) {
        $node = $this->root;
        for ($i = 0; $i < strlen($prefix); $i++) {
            $char = $prefix[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return true;
    }
}

$trie = new Trie();
$trie->insert("hello");
$trie->insert("world");
var_dump($trie->search("hello")); // true
var_dump($trie->startsWith("hell")); // true
var_dump($trie->search("worlds")); // false

Go语言也有Trie树的实现，可以使用map来模拟树的结构。下面是一个Go语言实现的Trie树的示例代码：

type TrieNode struct {
    Children map[byte]*TrieNode
    IsEndOfWord bool
}

type Trie struct {
    Root *TrieNode
}

func NewTrie() *Trie {
    return &Trie{Root: &TrieNode{Children: make(map[byte]*TrieNode)}}
}

func (t *Trie) Insert(word string) {
    node := t.Root
    for i := 0; i < len(word); i++ {
        char := word[i]
        if _, ok := node.Children[char]; !ok {
            node.Children[char] = &TrieNode{Children: make(map[byte]*TrieNode)}
        }
        node = node.Children[char]
    }
    node.IsEndOfWord = true
}

func (t *Trie) Search(word string) bool {
    node := t.Root
    for i := 0; i < len(word); i++ {
        char := word[i]
        if _, ok := node.Children[char]; !ok {
            return false
        }
        node = node.Children[char]
    }
    return node.IsEndOfWord
}

func (t *Trie) StartsWith(prefix string) bool {
    node := t.Root
    for i := 0; i < len(prefix); i++ {
        char := prefix[i]
        if _, ok := node.Children[char]; !ok {
            return false
        }
        node = node.Children[char]
    }
    return true
}

trie := NewTrie()
trie.Insert("hello")
trie.Insert("world")
fmt.Println(trie.Search("hello")) // true
fmt.Println(trie.StartsWith("hell")) // true
fmt.Println(trie.Search("worlds")) // false

AC自动机是基于Trie树的一种改进，可以在多个模式串中进行高效的匹配。它的基本思想是将多个模式串构建成一棵Trie树，并在每个节点上维护一个Fail指针，指向它的最长后缀节点。在匹配过程中，利用Fail指针进行快速跳转，避免重复匹配。

下面是一个Go语言实现的AC自动机的示例代码：

type ACNode struct {
    Children map[byte]*ACNode
    Fail *ACNode
    IsEndOfWord bool
}

type AC struct {
    Root *ACNode
}

func NewAC() *AC {
    return &AC{Root: &ACNode{Children: make(map[byte]*ACNode)}}
}

func (a *AC) Insert(word string) {
    node := a.Root
    for i := 0; i < len(word); i++ {
        char := word[i]
        if _, ok := node.Children[char]; !ok {
            node.Children[char] = &ACNode{Children: make(map[byte]*ACNode), Fail: a.Root}
        }
        node = node.Children[char]
    }
    node.IsEndOfWord = true
}

func (a *AC) Build() {
    queue := make([]*ACNode, 0)
    for _, child := range a.Root.Children {
        child.Fail = a.Root
        queue = append(queue, child)
    }
    for len(queue) > 0 {
        parent := queue[0]
        queue = queue[1:]
        for char, child := range parent.Children {
            fail := parent.Fail
            for fail != a.Root && fail.Children[char] == nil {
                fail = fail.Fail
            }
            if fail.Children[char] != nil {
                child.Fail = fail.Children[char]
            } else {
                child.Fail = a.Root
            }
            queue = append(queue, child)
        }
    }
}

func (a *AC) Search(text string) map[string]bool {
    result := make(map[string]bool)
    node := a.Root
    for i := 0; i < len(text); i++ {
        char := text[i]
        for node != a.Root && node.Children[char] == nil {
            node = node.Fail
        }
        if node.Children[char] != nil {
            node = node.Children[char]
        }
        if node.IsEndOfWord {
            result[text[i-len(word)+1:i+1]] = true
        }
        for fail := node.Fail; fail != a.Root && fail.IsEndOfWord; fail = fail.Fail {
            result[text[i-len(word)+len(word)-len(fail.Fail)+1:i+1]] = true
        }
    }
    return result
}

ac := NewAC()
ac.Insert("he")
ac.Insert("she")
ac.Insert("his")
ac.Insert("hers")
ac.Build()
fmt.Println(ac.Search("ushers")) // map[hers:true she:true he:true]

AC自动机的实现比Trie树稍微复杂一些，但是它在字符串匹配方面的性能比Trie树更优秀。