一、传统做法（循环匹配）

最常见写法：

foreach ($keywords as $word) {
    if (mb_strpos($text, $word) !== false) {
        // 命中
    }
}

假设：

• 关键词数量：M

• 文章长度：N

时间复杂度接近：

O(M × N)

如果：

• 文章 10KB

• 关键词 5000 个

那就是：

5000 × 10000 = 5000万次字符比较

而且还要重复扫描文本。

二、Aho-Corasick

AC 的特点是：

一次扫描文本，同时匹配所有关键词

复杂度：

构建阶段：O(关键词总长度)
匹配阶段：O(N + 匹配结果数)

注意：

匹配阶段与关键词数量几乎无关

这才是核心优势。

核心优势总结

1.  只扫描文本一次

传统方法：

• 每个关键词都扫描一遍文本

AC：

• 只扫描一遍文本

2.  关键词越多，优势越明显

3.  不会重复回退文本指针

传统：

每个词都会重新从头匹配。

AC：

• 利用 failure 指针

• 自动跳转

• 不重新扫描已经扫描过的字符

4.  复杂度对比总结

传统

O(M × N)

AC

O(N + 总关键词长度)

当 M 很大时：AC 几乎是“降维打击”。

举个真实场景

假设：

• 文章 20KB

• 敏感词 30000 条

传统方法

需要扫描：

30000 × 20000 = 6亿 次比较

AC 方法

只扫描：

20000 次

差距是 30000 倍。

三、什么时候不用 AC？

如果：

• 关键词 < 20 个

• 只匹配一次

• 性能要求不高

直接 strpos 反而更简单。

四、缺点

AC 也不是没有代价：

1. 构建 Trie 比较耗内存

2. 构建阶段较慢（一次性成本）

但：

一旦词库大于几百条
一旦是高并发
一旦是敏感词系统

AC 几乎是标准答案。

Aho-Corasick 原理简述

算法分三步：

1. 构建 Trie（字典树）

2. 构建 failure 指针

3. 扫描文本匹配

 Aho-Corasick PHP 实现（支持中文）

<?php

class AhoCorasick
{
    private array $trie = [];
    private array $fail = [];
    private array $output = [];

    public function __construct(array $keywords)
    {
        $this->buildTrie($keywords);
        $this->buildFailureLinks();
    }

    private function splitChars(string $str): array
    {
        return preg_split('//u', $str, -1, PREG_SPLIT_NO_EMPTY);
    }

    private function buildTrie(array $keywords): void
    {
        $this->trie = [[]];
        $this->output = [[]];

        foreach ($keywords as $word) {
            $node = 0;
            $chars = $this->splitChars($word);

            foreach ($chars as $char) {
                if (!isset($this->trie[$node][$char])) {
                    $this->trie[$node][$char] = count($this->trie);
                    $this->trie[] = [];
                    $this->output[] = [];
                }

                $node = $this->trie[$node][$char];
            }

            $this->output[$node][] = $word;
        }
    }

    private function buildFailureLinks(): void
    {
        $this->fail = array_fill(0, count($this->trie), 0);
        $queue = new SplQueue();

        foreach ($this->trie[0] as $node) {
            $queue->enqueue($node);
        }

        while (!$queue->isEmpty()) {
            $r = $queue->dequeue();

            foreach ($this->trie[$r] as $char => $u) {
                $queue->enqueue($u);

                $state = $this->fail[$r];

                while ($state && !isset($this->trie[$state][$char])) {
                    $state = $this->fail[$state];
                }

                if (isset($this->trie[$state][$char])) {
                    $this->fail[$u] = $this->trie[$state][$char];
                }

                $this->output[$u] = array_merge(
                    $this->output[$u],
                    $this->output[$this->fail[$u]]
                );
            }
        }
    }

    public function search(string $text): array
    {
        $results = [];
        $node = 0;
        $chars = $this->splitChars($text);

        foreach ($chars as $index => $char) {

            while ($node && !isset($this->trie[$node][$char])) {
                $node = $this->fail[$node];
            }

            if (isset($this->trie[$node][$char])) {
                $node = $this->trie[$node][$char];
            }

            foreach ($this->output[$node] as $word) {
                $wordLength = count($this->splitChars($word));

                $results[] = [
                    'word' => $word,
                    'position' => $index - $wordLength + 1
                ];
            }
        }

        return $results;
    }
}

使用示例

$keywords = ['程序员', '写代码', '老程序员'];

$ac = new AhoCorasickUtf8($keywords);

$text = "老程序员还在写代码";

$result = $ac->search($text);

print_r($result);

输出：

Array
(
    [0] => Array
        (
            [word] => 老程序员
            [position] => 0
        )

    [1] => Array
        (
            [word] => 程序员
            [position] => 1
        )

    [2] => Array
        (
            [word] => 写代码
            [position] => 6
        )

)