蓝桥杯刷题 Day2 AC自动机（二次加强版）

---

---

前言

今天写牛客网模板题中的字符串模块

---

完整代码

import java.util.*;// 定义结构体，用来构建树
class TrieNode{TrieNode[] children = new TrieNode[26]; // 子节点数组TrieNode fail; // 失败指针（类似于KMP中的next数组）int cnt = 0; // 统计子节点访问的次数List<Integer> ids = new ArrayList<>(); // 创建了一个动态数组，专门存储int类型，并通过list接口列表来引用
}public class Main {public static void main(String[] args){// 输入Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 输入模式串个数String[] patterns = new String[n]; // 输入模式串for(int i = 0; i < n; i++){patterns[i] = scanner.next();}String s = scanner.next(); // 输入文本串// 构建Tire树TrieNode root = new TrieNode(); // 创建根节点List<TrieNode> nodesOrder = new ArrayList<>(); // 记录所有节点的处理顺序（用于后续拓扑排序）TrieNode[] endNodes = new TrieNode[n]; // 记录每个模式串的结束节点for(int i = 0; i < n; i++){String p = patterns[i]; // 记录每个模式串TrieNode curr = root; // 记录节点// 将p转换成字符数组并遍历for(char c:p.toCharArray()){int idx = c - 'a'; // 将字符映射成ASCII值，便于记录// 若子节点不存在则创建if(curr.children[idx] == null){curr.children[idx] = new TrieNode();}curr = curr.children[idx];}curr.ids.add(i); // 将当前模式串索引添加到结束节点的ids列表中endNodes[i] = curr; // 保存结束节点？}// 构建失败指针（BFS层级遍历）/** 使用队列管理Trie树节点的处理顺序* 队列用于按层或按广度优先顺序（BFS）处理节点* Queue是一种数据结构，遵循先进先出（FIFO）的插入顺序* */// 接口                      具体实现Queue<TrieNode> queue = new LinkedList<>();root.fail = null;// 初始化根节点的子节点for (int i = 0; i < 26; i++) {if(root.children[i] != null){root.children[i].fail = root; // 失败指针指向根queue.add(root.children[i]);}}// isEmpty判断为空，poll取出队列头部节点while(!queue.isEmpty()){TrieNode curr = queue.poll();nodesOrder.add(curr); // 记录节点处理顺序// 遍历**当前节点**的所有子节点for (int i = 0; i < 26; i++) {TrieNode child = curr.children[i];if(child != null){TrieNode fail = curr.fail;// 若fail存在但fail没有对应字符i的子节点，则沿着失败指针链向上回溯。while(fail != null && fail.children[i] == null){fail = fail.fail;}// 否则，指向fail的字符i子节点，即最长后缀的末尾节点。child.fail = (fail == null) ? root : fail.children[i];queue.add(child); // 子节点入队}}}// 匹配文本串，统计cntTrieNode curr = root;for(char c:s.toCharArray()){int idx = c - 'a';while(curr != root && curr.children[idx] == null){curr = curr.fail;}if(curr.children[idx] != null){curr = curr.children[idx];}curr.cnt++;}// 拓扑排序优化（逆序累加）for (int i = nodesOrder.size() - 1; i >= 0 ; i--) {TrieNode node = nodesOrder.get(i);if(node.fail != null){// 将当前节点的cnt累加到失败指针节点的cnt中node.fail.cnt += node.cnt;}}// 输出for (int i = 0; i < n; i++) {System.out.println(endNodes[i].cnt);}}}

一、AC自动机（二次加强版）

原题地址: AC自动机（二次加强版）

1. 解题思路

1.1 问题抽象：

在一篇文章（文本串）中查找多个单词（模式串）对应的位置
核心思想：Trie树和失败指针

1.2 解题步骤

1. Tire树构建：一种树形结构，用来存放多个单词
2. 失败指针：查找失败后回退
3. 文本匹配与统计：用文本串s在Trie树上走
4. 拓扑排序：全局统计，从底向上统计

2. 拆解代码

2.1结构体

// 定义结构体，用来构建树
class TrieNode{TrieNode[] children = new TrieNode[26]; // 子节点数组TrieNode fail; // 失败指针（类似于KMP中的next数组）int cnt = 0; // 统计子节点访问的次数List<Integer> ids = new ArrayList<>(); // 创建了一个动态数组，专门存储int类型，并通过list接口列表来引用
}

2.2 输入

 // 输入Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 输入模式串个数String[] patterns = new String[n]; // 输入模式串for(int i = 0; i < n; i++){patterns[i] = scanner.next();}String s = scanner.next(); // 输入文本串

2.3 Trie树的创建

1. 将模式串分为根节点和子节点，为了输出模式串T在文本串S中出现的次数，需要记录模式串的结束结点和节点的处理顺序

 // 构建Tire树TrieNode root = new TrieNode(); // 创建根节点List<TrieNode> nodesOrder = new ArrayList<>(); // 记录所有节点的处理顺序（用于后续拓扑排序）TrieNode[] endNodes = new TrieNode[n]; // 记录每个模式串的结束节点for(int i = 0; i < n; i++){String p = patterns[i]; // 记录每个模式串TrieNode curr = root; // 记录节点// 将p转换成字符数组并遍历for(char c:p.toCharArray()){int idx = c - 'a'; // 将字符映射成ASCII值，便于记录// 若子节点不存在则创建if(curr.children[idx] == null){curr.children[idx] = new TrieNode();}curr = curr.children[idx];}curr.ids.add(i); // 将当前模式串索引添加到结束节点的ids列表中endNodes[i] = curr; // 保存结束节点？}

2.4 构建失败指针（BFS层级遍历）

// 构建失败指针（BFS层级遍历）/** 使用队列管理Trie树节点的处理顺序* 队列用于按层或按广度优先顺序（BFS）处理节点* Queue是一种数据结构，遵循先进先出（FIFO）的插入顺序* */// 接口                      具体实现Queue<TrieNode> queue = new LinkedList<>();root.fail = null;// 初始化根节点的子节点for (int i = 0; i < 26; i++) {if(root.children[i] != null){root.children[i].fail = root; // 失败指针指向根queue.add(root.children[i]);}}// isEmpty判断为空，poll取出队列头部节点while(!queue.isEmpty()){TrieNode curr = queue.poll();nodesOrder.add(curr); // 记录节点处理顺序// 遍历**当前节点**的所有子节点for (int i = 0; i < 26; i++) {TrieNode child = curr.children[i];if(child != null){TrieNode fail = curr.fail;// 若fail存在但fail没有对应字符i的子节点，则沿着失败指针链向上回溯。while(fail != null && fail.children[i] == null){fail = fail.fail;}// 否则，指向fail的字符i子节点，即最长后缀的末尾节点。child.fail = (fail == null) ? root : fail.children[i];queue.add(child); // 子节点入队}}}

2.5 匹配文本串

// 匹配文本串，统计cntTrieNode curr = root;for(char c:s.toCharArray()){int idx = c - 'a';while(curr != root && curr.children[idx] == null){curr = curr.fail;}if(curr.children[idx] != null){curr = curr.children[idx];}curr.cnt++;}

2.6 拓扑排序

  // 拓扑排序优化（逆序累加）for (int i = nodesOrder.size() - 1; i >= 0 ; i--) {TrieNode node = nodesOrder.get(i);if(node.fail != null){// 将当前节点的cnt累加到失败指针节点的cnt中node.fail.cnt += node.cnt;}}

2.6 输出

        // 输出for (int i = 0; i < n; i++) {System.out.println(endNodes[i].cnt);}

3. 题后收获

3.1 知识点

1. 创建一个列表，用于按顺序存储指定类型的对象：List nodesOrder = new ArrayList<>();
2. 将p转换成字符数组并遍历：for(char c:p.toCharArray())
3. 将当前模式串索引添加到结束节点的ids列表中：curr.ids.add(i)
4. 将字符映射成ASCII值，便于记录：int idx = c - ‘a’
5. 用于队列的数据结构：Queue queue = new LinkedList<>()
6. isEmpty()判断为空，poll()取出队列头部节点