根据🔗AC算法原理，PHP的实现，我们定义下面几个类

  • NodeData：用来存储节点的值，之所以顶一个类来存，是为了避免PHP的参数传递是默认是值传递导致无法修改节点的值

  • TrieNode：前缀树的一个节点，记录节点的跳转条件和目标节点引用、失败节点引用、节点数据等

  • Trie：前缀树，主要方法都在这

最重要的 Trie，关键的几个方法

  • ​addWord($word, $data)​：构建关键字和节点数据的关系

  • ​makeAutomation()​：构建失败转移关系

  • ​match($str)​：传入关键字，找结果

最终代码

<?php
/**
 * Aho-Corasick算法
 */
namespace AC;

use Exception;

// 节点
class TrieNode {
  public $end = false;      // 是否是结束节点
  public $nodeData = null;  // 当前节点的数据，这是一个NodeData对象
  public $deep = 0;         // 深度
  public $next = [];        // 根据字符，成功转到的下一个状态节点
  public $failNode = null;  // 失败时跳转的下一个状态

  public function __construct() {
    $this->nodeData = new NodeData();
  }

  public function toString() {
    return "end: " . ($this->end ? 'true' : 'false') . ", deep: " . $this->deep . ", next: [" . implode(',', array_keys($this->next)) . "], failNode: " . (empty($this->failNode) ? 'false' : 'true') . "\n";
  }
}

// 节点的数据，将数据封装成一个对象，是为了使用对象的引用传值方式
class NodeData {
  public $data = null;
}

// trie树
class Trie {
  private $isMake = false;   // 是否已经创建了自动机
  private $root;             // 根节点
  private $nodeArray = [];   // 节点数组
  private $oneDeepNodeArray = []; // 深度是1的节点数组 

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

  /**
   * 添加一个关键字以及它对应的数据
   * @param string $word 关键字
   * @param mixed $data 关键字对应的数字
   */
  public function addWord($word, $data) {
    // 如果自动机已创建，则不可再添加
    if ($this->isMake) {
      throw new Exception("Automaton created, no more can be added.");
    }

    $len = mb_strlen($word);
    $pos = $this->root;
    for ($i = 0; $i < $len; $i++) {
      $ch = mb_substr($word, $i, 1);
  
      if (!isset($pos->next[$ch])) {
        $node = new TrieNode();
        $node->deep = $i + 1;
        $this->nodeArray[] = $node;
  
        // 如果是深度为1
        if ($node->deep === 1) {
          $node->failNode = $this->root; // 设置失败跳转节点为根节点
          $this->oneDeepNodeArray[] = $node;
        }

        $pos->next[$ch] = $node;
      } else {
        $node = $pos->next[$ch];
      }

      if ($i === $len - 1) {
        $node->end = true;
        $node->nodeData->data = $data;
      }

      $pos = $pos->next[$ch];
    }
  }

  /**
   * 检查关键字是否存在
   * @param string $word 关键字
   * @return bool 存在则返回true，否则返回false
   */
  public function checkWord($word) {
    $len = mb_strlen($word);
    $pos = $this->root;
    $ok = false;
    for ($i = 0; $i < $len; $i++) {
      $ch = mb_substr($word, $i, 1);

      if (isset($pos->next[$ch])) {
        $pos = $pos->next[$ch];
      } else {
        break;
      }

      if ($i === $len - 1 && $pos->end) {
        $ok = true;
      }
    }

    return $ok;
  }

  /**
   * 获取关键字的数据
   * @param string $word 关键字
   * @return NodeData 关键字存在则返回对应节点的数据对象，否则返回null
   */
  public function getNodeData($word) {
    $len = mb_strlen($word);
    $pos = $this->root;
    $data = null;
    for ($i = 0; $i < $len; $i++) {
      $ch = mb_substr($word, $i, 1);

      if (isset($pos->next[$ch])) {
        $pos = $pos->next[$ch];
      } else {
        break;
      }

      if ($i === $len - 1 && $pos->end) {
        $data = $pos->nodeData;
      }
    }

    return $data;
  }

  /**
   * 修改关键字对应的数据对象(NodeData)的数据
   * @param string $word 关键字
   * @param mixed $data 数据
   * @return bool 关键字存在则返回true，否则返回false
   */
  public function setNodeData($word, $data) {
    $len = mb_strlen($word);
    $pos = $this->root;

    $isOk = false;
    for ($i = 0; $i < $len; $i++) {
      $ch = mb_substr($word, $i, 1);

      if (isset($pos->next[$ch])) {
        $pos = $pos->next[$ch];
      } else {
        break;
      }

      if ($i === $len - 1 && $pos->end) {
        $pos->nodeData->data = $data;
        $isOk = true;
      }
    }

    return $isOk;
  }

  /**
   * 构建自动机，计算每个节点的失败跳转节点
   */
  public function makeAutomation() {
    if ($this->isMake) {
      return;
    }

    // 队列初始化为全部是深度为1的节点
    $nodeQuery = $this->oneDeepNodeArray;

    $front = 0; // 队列头指针
    while (!empty($nodeQuery)) {
      $r = $nodeQuery[$front];
      unset($nodeQuery[$front]);
      $front++;

      foreach ($r->next as $ch => $s) {
        $nodeQuery[] = $r->next[$ch]; // 入队
  
        // 寻找$s的失败跳转节点
        $state = $r->failNode; // $s的上一个节点的失败跳转节点
        while (!isset($state->next[$ch]) && $state->deep !== 0) { // 如果这个节点输入$ch也没有可到达的节点，并且不是根节点，则继续找这个节点的失败跳转节点
          $state = $state->failNode;
        }
        if (isset($state->next[$ch])) {
            $r->next[$ch]->failNode = $state->next[$ch];
        } else {
            $r->next[$ch]->failNode = $state;
        }
      }
    }

    $this->isMake = true;
  }

  /**
   * 对字符串进行匹配
   * @param string $str 要进行匹配的字符串
   * @return array 返回数组，元素是匹配到的关键字对应的开始位置以及关键字对应的数据
   */
  public function match($str) {
    $result = [];
    $strLen = mb_strlen($str);

    $node = $this->root;
    for ($i = 0; $i < $strLen; $i++) {
      $ch = mb_substr($str, $i, 1);

      while (!isset($node->next[$ch]) && $node->deep !== 0) { // 没有可跳转的节点，并且该节点不是跟节点，则跳转到失败跳转节点
        $node = $node->failNode;
      }

      if (isset($node->next[$ch])) { // 有匹配的则跳转到下一个节点
        $node = $node->next[$ch];
        if ($node->end) {
          $result[] = [
            'start_index'   => $i + 1 - $node->deep,
            'data'          => $node->nodeData->data
          ];
        }
      }
    }

    return $result;
  }
}

$trie = new Trie();
$trie->addWord("西红柿", "西红柿");
$trie->addWord("菠萝", "菠萝");
$trie->addWord("西红柿子", "西红柿子");
$trie->addWord("西瓜", "西瓜");
$trie->addWord("西瓜汁", "西瓜汁");

$trie->makeAutomation();
$ret = $trie->match("我喜欢吃西红柿子和西瓜汁哈哈哈");
var_dump($ret);

$ret = $trie->match("不不不，我更细化菠萝蜜");
var_dump($ret);