【算法&数据结构体系篇class32】：IndexTree & AC自动机

た入场券 2024-03-22 08:54 107阅读 0赞

### 一、IndexTree ###

> 特点：
> 
> 1）支持区间查询
> 
> 2）没有线段树那么强，但是非常容易改成一维、二维、三维的结构
> 
> 3）只支持单点更新

###  ###

### 二、IndexTree 一维数组代码演示 ###

package class32;
 
 /**IndexTree
 * 特点：
 * 1）支持区间查询
 * 2）没有线段树那么强，但是非常容易改成一维、二维、三维的结构
 * 3）只支持单点更新
 *
 * 时间复杂度 O(logN)
 */
 public class IndexTree {
 /**
 * tree数组的赋值演示：
 * 原数组arr[ 2，3，4，6，7，5，9，3，7，9 ] 这里的索引位置对应 1,2,3,4,5,6,7,8,9,10 10个数
 *
 * tree对应索引情况：
 * 1位置包含 原数组1位置 值为2 1位置前面没有位置 所以包含1位置自身
 * 2位置包含 1-2位置 值为2+3 2位置前面1位置 长度都是1个数 合并成一组变成2个数 所以2位置包含1-2
 * 3位置包含 3 位置 值为4 3位置前面是1-2位置组成的长度2个数的组 3位置只有一个数 不能合并 所以只包含3当前位置
 * 4位置包含 1-4位置 值为2+3+4+6 4位置前面是3位置长度1个数的组 与4位置当前一个数长度相等 合并成一组变成2个数 此时是3-4，再往前看 右1-2组成的长度2个数的组 与当前3-4长度一致 所以可以合并 包含1-4的长度4个数的组
 * 5位置包含 5 7 5 同理 只有自己成组
 * 6 5-6 7+5 6 同理 与前面5 的长度一个数组可以合并成为 包含5-6的组长度2个数 再往前是1-4的长度4的组 长度不一致不能合并 所以是5-6范围
 * 7 7 9 7 同理 前面长度2的组 不能合并 只有当前位置本身一个数
 * 8 1-8 2+3+4+6+7+5+9+33 8 同理 与前面位置 长度一个数的7位置合并 包含7-8的组 再往前与5-6组合并 形成5-8的长度4的组 再往前与1-4的长度4个数的组合并 形成包含1-8的长度8的组 所以当前位置8包含1-8的数
 * ...
 */
 
 public static class iTree{
 private int[] tree; //树结构数组
 private int n; //数组实际个数
 public iTree(int size){
 n = size;
 tree = new int[size +1]; //树结构默认去掉0位置 从1位置开始 所以长度+1
 }
 
 //求和方法 将1...index 累加求和
 public int sum(int index){
 int res = 0; //定义结果变量
 
 //开始进行累加 tree[index] 值是包含哪个区间的数 可能就是index本身一个数 也可能是i...index区间的数 也可能是1..i..index包含全部从头至index的数 根据前面的演示来分析
 //比如要求1--8 那么tree[8] 就是1-8的求和值
 //比如要求1-6 那么tree[6] 是5-6的求和值 还有加上 tree[4] 1-4的求和值 就需要分段累加
 //分段累加的位置怎么定义 就有公式 将index 依次减去其二进制位最右侧1的二进制数 直到0 每个值就是各个区间段的求和
 //比如 index = 8 1000 先加上当前位置的值tree[8] 减去最右侧1的二进制 就是1000 得到0 就退出 所以值就是tree[8]
 //比如 index = 6 0110 先加上当前位置的值tree[6] 减去最右侧1的二进制 就是0010 得到0100 还没到0 继续
 // 0100 就是4 先加上当前位置的值tee[4] 减去最右侧1的二进制 就是0100 得到0 就退出 所以值就是tree[6]+tree[4]
 //所以需要依次根据index 的向前移动公式 进行分段累加 直到完成1...index区间累加和
 while (index > 0){
 //结果集累加
 res += tree[index];
 //向前刷新index 依次减去最右侧的二进制位上的1 直到index来到0跳出循环
 //-index 就是 ~index +1 取反+1 接着在与运算index 就能提出index 最右侧1
 //比如index : 0011001000
 // -index (~index+1): 1100111000
 //index & -index : 0000001000 就取出了index最右侧1 的二进制数
 index -= index & (-index);
 }
 return res;
 }
 
 
 //添加数方法 在index位置加入数num
 //注意 添加到tree数组的时候 由于我们tree数组的定义 index位置的影响 可能有多个位置索引影响 需要对每个影响的位置都加上num
 //比如 在 3位置 加入 2 首先 小于3位置的1 2肯定不会影响 因为 索引的值范围是不会超过当前索引的 最右范围就是包含自身 不会再往右了
 //那么还有哪些位置 包含3 比如 4位置 就是3-4位置的求和 8位置 就是1-8位置的求和 16位 就是1-16位置的求和..最后不超过整个数组n 比如n就在15 那么影响的位置就是 3 4 8 需要对这两个位置刷新
 //所以这个位置 就有对应的公式 需要向后移动的公式 分段进行累加 直到超过n长度范围
 //与求和的公式类似 同样是用到 index二进制最右侧1的二进制数 这里就不是减 而是加 N假设15
 //比如 index = 3 num=2 n= 15
 // 0011 2先加上当前位置的值tree[3] +最右侧1的二进制 就是0001 得到0100 4<15 继续
 // 0100 就是4 2先加上当前位置的值tee[4] +最右侧1的二进制 就是0100 得到1000 8<15 继续
 //1000 就是8 2先加上当前位置的值tee[8] +最右侧1的二进制 就是1000 得到10000 16>15 退出
 //最后得到 影响3位置的 有 3 4 8 三个位置 进行分别加上2
 
 public void add(int index, int num){
 //index 根据公式向后移动 不超过整个数组最后的索引n n是个数 同时也可以作为最后一个位置的索引
 while (n >= index){
 //对影响的位置累加num
 tree[index] += num;
 //index位置往后滚动
 index += index & (-index);
 }
 }
 }
 
 public static class Right {
 private int[] nums;
 private int N;
 
 public Right(int size) {
 N = size + 1;
 nums = new int[N + 1];
 }
 
 public int sum(int index) {
 int ret = 0;
 for (int i = 1; i <= index; i++) {
 ret += nums[i];
 }
 return ret;
 }
 
 public void add(int index, int d) {
 nums[index] += d;
 }
 
 }
 
 public static void main(String[] args) {
 int N = 100;
 int V = 100;
 int testTime = 2000000;
 iTree tree = new iTree(N);
 Right test = new Right(N);
 System.out.println("test begin");
 for (int i = 0; i < testTime; i++) {
 int index = (int) (Math.random() * N) + 1;
 if (Math.random() <= 0.5) {
 int add = (int) (Math.random() * V);
 tree.add(index, add);
 test.add(index, add);
 } else {
 if (tree.sum(index) != test.sum(index)) {
 System.out.println("Oops!");
 }
 }
 }
 System.out.println("test finish");
 }
 
 }

### 三、IndexTree 二维数组代码演示 ###

package class32;
 
 /**
 * IndexTree 改二维数组
 * // 测试链接：https://leetcode.com/problems/range-sum-query-2d-mutable
 *
 * 时间复杂度 O(logN) * O(logM)
 */
 public class IndexTree2D {
 private int[][] tree; //二维数组的树结构数组
 private int[][] nums; //拷贝题目传递的二维数组保存下来
 private int n; // nums数组的行数 同时对应tree数组的最后行索引位置
 private int m; // nums数组的列数 对应tree数组的最后列索引位置
 
 public IndexTree2D(int[][] matrix) { //构造函数
 n = matrix.length;
 m = matrix[0].length;
 tree = new int[n + 1][m + 1]; //tree数组下标默认从1开始 0不用 所以长度+1
 nums = new int[n][m]; //深拷贝 入参数组matrix
 for (int i = 0; i < n; i++) {
 for (int j = 0; j < m; j++){
 //遍历传递的二维数组 将每个位置的值，都更新到我们tree 和 nums数组中
 update(i,j,matrix[i][j]);
 }
 }
 }
 
 //刷新原数组row行 col列的值为val
 public void update(int row, int col, int val){
 if(n == 0 || m == 0) return; //是否刷新 需要先判断我们数组长度
 int add = val - nums[row][col]; //修改值转换成 添加 用来刷新tree数组值 当前nums[row][col]值修改成matrix[row][col]=val的值 那么加多少 就是可以将修改后的val- 当前的nums[row][col]值
 nums[row][col] = val; //刷新nums的拷贝数组值
 
 //二维数组 刷新tree数组 相关的是哪几列几行，就是将每一行 每一列 按照一维数组的相关公式依赖去向右滚动i j 位置 遍历 row * col就有这么多个位置需要累加
 for(int i = row+1; i <= n; i+= i & (-i) ){
 for(int j= col+1; j <= m; j+= j & (-j)){
 //遍历i 行 r列 起始下标要+1 因为定义结果中 tree是索引从1...n/m 对应原数组0...n-1/m-1
 tree[i][j] += add;
 }
 }
 }
 
 //返回数组 1,1...到row,col 位置的求和值
 public int sum(int row, int col){
 int res = 0; //定义一个结果集
 
 //二维数组 累加对应位置的tree数组 相关的是哪几列几行，就是将每一行 每一列 按照一维数组的相关公式依赖去向左滚动i j 位置 遍历 row * col就有这么多个位置需要累加
 for(int i = row +1; i >0; i -= i & (-i)){
 for(int j = col + 1; j >0; j-= j & (-j)){
 //遍历i 行 r列 起始下标要+1 因为定义结果中 tree是索引从1...n/m 对应原数组0...n-1/m-1
 res += tree[i][j];
 }
 }
 return res;
 }
 
 //求返回数组 某个位置row1,col1 到 row2,col2的 求和数 不再是从1,1开始
 //sum(row2,col2) 值为 1,1 --> row2,col2
 //sum(row1,col1) 值为 1,1 --> row1,col1
 //假设 3,3 -> 4,4 的求和数 那么这个矩阵其实就是在 1,1->4,4大矩阵的内侧
 //需要减去其他位置的值
 // x x x x
 // x x x ,
 // x x 1 2
 // x . 3 4
 // 如图： sum(4,4) 就是整个矩阵值 而标记x的都是不需要的
 // 另外要减去 sum(4,2) 也就是标记. 到左上角x的矩阵 2*4=8个
 // 再减去 sum(2,4) 也就是标记, 到左上角x的矩阵 4*2=8个
 //这里面 左上角2*2的矩阵 重复减多1次 所以再加上sum(2,)的值
 //就得到了 3,3到4,4的求和值了
 public int sumRegion(int row1, int col1, int row2, int col2){
 return sum(row2,col2) - sum(row2,col1-1) - sum(row1 - 1,col2) + sum(row1 -1,col1-1);
 }
 
 
 }

###  ###

### 四、AC自动机 ###

> 解决在一个大字符串中，找到多个候选字符串的问题

> **AC****自动机算法核心**：
> 
> 1）把所有匹配串生成一棵前缀树
> 
> 2）前缀树节点增加fail指针
> 
> 3）fail指针的含义：如果必须以当前字符结尾，当前形成的路径是str，剩下哪一个字符串的前缀和str的后缀，拥有最大的匹配长度。fail指针就指向那个字符串的最后一个字符所对应的节点。

**1、获取候选字符串数组 有多少个字符串 是包含在大文章字符串中的 返回符合的数量**

package class32;
 
 import java.util.LinkedList;
 import java.util.Queue;
 
 /**AC自动机
 * 解决在一个大字符串中，找到多个候选字符串的问题
 * 
 * AC自动机算法核心
 * 1）把所有匹配串生成一棵前缀树
 * 
 * 2）前缀树节点增加fail指针
 * 
 * 3）fail指针的含义：如果必须以当前字符结尾，当前形成的路径是str，剩下哪一个字符串的前缀和str的后缀，拥有最大的匹配长度。fail指针就指向那个字符串的最后一个字符所对应的节点。
 */
 public class AC1 {
 
 //支持返回候选字符串有多少个是包含在大文章字符串中的 返回数量
 
 //前缀树节点
 public static class Node{
 private int end; //end表示当前字符串节点结尾的个数 如果有则当前节点节点 累加
 private Node fail; // fail指针节点，是AC自动机的一个核心指针 指向下个遍历节点
 private Node[] next; //前缀树数组节点 记录每个字符串的依次指向
 
 public Node(){ //构造函数 初始化
 end = 0;
 fail = null;
 next = new Node[26];
 }
 }
 
 //定义AC自动机的类
 public static class ACAutomation {
 //定义一个前缀树类节点
 private Node root;
 
 public ACAutomation(){
 root = new Node();
 }
 
 //添加候选的字符串，构建前缀树数组 比如有多个字符串 abc, edc,ijn等 依次先通过insert方法添加 完善好前缀树数组
 public void insert(String s){
 char[] str = s.toCharArray(); //转换字符数组
 Node cur = root; //当前节点指向root
 int index = 0;
 for(int i = 0; i < str.length; i++){
 index = str[i] - 'a'; //遍历当前每个字符的位置
 if(cur.next[index] == null){
 cur.next[index] = new Node(); //如果当前位置还未构建节点 那就赋值初始化节点
 }
 cur = cur.next[index]; //再将当前节点位置指向来到当前遍历的子字符位置
 }
 cur.end++; //最后遍历完整个字符之后，再最后的字符节点位置的end值加1 表示当前结尾的字符 是一个候选字符串
 }
 
 //待我们将需要匹配的候选字符串都通过insert方法都添加到AC自动机类中 构建好前缀树数组后
 //我们再通过build方法 给当前前缀树 完善其 fail的指针指向内容
 public void build() {
 Queue<Node> queue = new LinkedList<>(); //定义队列集合
 queue.add(root); //增加当前root节点入队列 进行宽度优先遍历前缀树 同时完善fail指针
 Node cur = null; //定义当前节点 进行辅助遍历
 Node cfail = null; //定义当前节点的fail指针 辅助
 while(!queue.isEmpty()){
 cur = queue.poll(); //弹出队列节点 此时cur是表示父节点 依次去完善其子节点的 fail指针
 for(int i = 0; i < 26; i++){ //依次遍历每一层节点路径 有26个字符进行遍历
 if(cur.next[i] != null){ //当下个子节点存在的时候 进行逻辑分析
 cur.next[i].fail = root; //先将子节点的fail指向root 后续如果有存在的真实节点指向在后面会修改
 cfail = cur.fail; //当前子节点的fail先指向父节点的fail
 while(cfail != null){ //遍历cfail指向直到空就退出 如果其next[i]位置非空 那么就说明是实际的fail指向 刷新 cur.next[i].fail
 if(cfail.next[i] != null){
 cur.next[i].fail = cfail.next[i];
 break; //找到之后 直接退出循环
 }
 cfail = cfail.fail; //没有找到 就接着遍历fail指向循环下去
 }
 queue.add(cur.next[i]); // 最后将当前i位置的子节点存在的 就加入队列 继续下层遍历
 }
 }
 }
 
 }
 
 //当候选要判断的字符串都通过insert方法 构建好了前缀树 以及通过build构建好对应的fail指向节点后 整个AC自动机就已经完成
 //接着就是判断这些字符串 是否都包含在目标大文章字符串内 并返回包含在内的字符串数量
 public int containNum(String content){
 char[] str = content.toCharArray(); //大文章字符串转换字符数组
 Node cur = root; //定义cur节点指向root 进行依次遍历
 Node follow = null; //定义follow节点用于指向cur 进行fail指向遍历 目的是不影响cur的位置
 int res = 0; //结果数量
 int index = 0; //nexts数组位置 下个子节点字符位置
 for(int i = 0; i < str.length; i++){ //开始遍历字符路径
 index = str[i] - 'a'; //字符对应的索引
 while(cur.next[index] == null && cur != root){ //开始遍历cur对应的下个子字符next[index]如果空 且cur非根节点 那么就cur指向fail节点进行循环遍历
 cur = cur.fail;
 }
 //那么来到这里 可能是next[index]非空 存在值 或者cur走回到root 那么就根据两个情况刷新cur
 cur = cur.next[index] != null ? cur.next[index] : root;
 follow = cur; //此时follow节点指向cur 进行前置的fail指向遍历 去判断是否存在候选字符串
 while(follow != root){ //从当前follow节点开始往前遍历 直到回到root就退出 因为root.fail指向是空 需要再遍历
 if(follow.end == -1){
 break; //如果遍历到当前节点的end值是-1 说明被标记添加过了 后续的就不用再遍历了 直接退出当前循环
 }
 {
 res += follow.end; //因为end默认值0 可以直接累加 不管是否是字符串结尾
 follow.end = -1; //并且将当前位置的end设置-1 再下次的遍历中 就不再重复遍历前面已经走过的fail指针了 节省时间
 
 }
 
 
 follow = follow.fail;
 }
 }
 return res;
 }
 }
 
 public static void main(String[] args) {
 ACAutomation ac = new ACAutomation();
 ac.insert("dhe");
 ac.insert("he");
 ac.insert("c");
 ac.build();
 System.out.println(ac.containNum("cdhe"));
 }
 }

**2、获取候选字符串数组 有哪些字符串 是包含在大文章字符串中的 返回符合的字符串集合**

package class32;
 
 import java.util.ArrayList;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Queue;
 
 /**AC自动机
 * 解决在一个大字符串中，找到多个候选字符串的问题
 * 
 * AC自动机算法核心
 * 1）把所有匹配串生成一棵前缀树
 * 
 * 2）前缀树节点增加fail指针
 * 
 * 3）fail指针的含义：如果必须以当前字符结尾，当前形成的路径是str，剩下哪一个字符串的前缀和str的后缀，拥有最大的匹配长度。fail指针就指向那个字符串的最后一个字符所对应的节点。
 */
 public class AC2 {
 //支持返回候选字符串有哪些是包含在大文章字符串中的 返回字符串内容
 
 //定义前缀树的节点
 public static class Node {
 private String end; //表示当前节点是否作为 候选字符串的结尾 如果是 那么end就是该字符串 否则就是空
 private boolean endUse; //表示当前节点作为候选字符串结尾时，是否被加入过集合中 true则表示加入 后续循环遍历到则可以减少遍历直接退出
 private Node fail; //fail指针节点，是AC自动机的一个核心指针 指向下个遍历节点
 private Node[] nexts; //前缀树数组节点 记录每个字符串的依次指向
 
 public Node() { //构造函数 初始化
 end = null;
 endUse = false;
 fail = null;
 nexts = new Node[26]; //数组 定义字符都是小写或大写 一共26个长度
 }
 }
 
 
 //定义AC自动机的类
 public static class ACAutomation {
 private Node root; //定义一个根节点
 
 public ACAutomation() { //构造函数 初始化节点
 root = new Node();
 }
 
 //添加候选的字符串，构建前缀树数组 比如有多个字符串 abc, edc,ijn等 依次先通过insert方法添加 完善好前缀树数组
 public void insert(String s) {
 char[] str = s.toCharArray(); //将候选字符串转换成字符数组
 Node cur = root; //将cur节点指向root节点 用来从根节点开始遍历
 int index = 0; //遍历前缀树数组nexts的索引
 for (int i = 0; i < str.length; i++) { // 依次遍历每个字符
 index = str[i] - 'a'; //获取每个字符 转换对应的索引位置
 if (cur.nexts[index] == null) {
 cur.nexts[index] = new Node(); //如果所加的字符 当前路径数组没有对应节点 那么就给他初始化一个节点对象
 }
 
 //然后将当前节点往下个节点位置滚动 依次将这个str每个字符都给串起来 指向对应索引位置的nexts数组
 //如果前面cur.nexts[index]已经有路径非空 也是同样的将cur节点来到下个字符位置
 cur = cur.nexts[index];
 }
 //nexts数组遍历填充完成后 在cur来到最后一个字符位置 的end字符串标识 赋值当前添加的字符串s
 cur.end = s;
 }
 
 //待我们将需要匹配的候选字符串都通过insert方法都添加到AC自动机类中 构建好前缀树数组后
 //我们再通过build方法 给当前前缀树 完善其 fail的指针指向内容
 public void build() {
 Queue<Node> queue = new LinkedList<>(); //构建一个队列集合 用来进行宽度优先遍历前缀树
 queue.add(root); //先将root AC自动机的根节点加入队列集合
 Node cur = null; //定义当前树节点 赋值变量 用来接收遍历的当前节点
 Node cfail = null; //定义当前树节点fail指针的指向节点
 while (!queue.isEmpty()) {
 cur = queue.poll(); //弹出当前这个节点 作为一个父节点
 for (int i = 0; i < 26; i++) { //遍历全部自负路径
 if (cur.nexts[i] != null) { //当遇到当前i字符位置 非空 说明是有节点字符
 cur.nexts[i].fail = root; //我们先把当前nexts数组子字符的fail指向到root 节点 后面如果有其对应的一个指向节点 后面会刷新
 cfail = cur.fail; //当前这个子节点的fail指向赋值为父节点的fail指向cur.fail
 while (cfail != null) { //遍历cfail 依次指向其fail指向 直到回到root root.fail=null 到空则跳出循环
 if (cfail.nexts[i] != null) { //如果cfail指向的 下个子节点非空 那么这个就是当前子节点的fail指向
 cur.nexts[i].fail = cfail.nexts[i];
 break; //找到后就直接退出
 }
 cfail = cfail.fail; //没有找到就继续指向fail下个节点 最后如果都没找到cfail指向就是指向null
 }
 queue.add(cur.nexts[i]); //接着将当前对应的下个子节点字符加入 队列进行遍历
 }
 }
 }
 }
 
 //当候选要判断的字符串都通过insert方法 构建好了前缀树 以及通过build构建好对应的fail指向节点后 整个AC自动机就已经完成
 //接着就是判断这些字符串 是否都包含在目标大文章字符串内 并返回list集合 包含在内的这些字符串
 public List<String> containWords(String content) {
 char[] str = content.toCharArray(); //字符串转换字符数组
 List<String> res = new ArrayList<>(); //定义结果集
 Node cur = root; //定义cur节点指向root 进行依次遍历
 Node follow = null; //定义follow节点用于指向cur 进行fail指向遍历 目的是不影响cur的位置
 int index = 0; //nexts数组位置 下个子节点字符位置
 for (int i = 0; i < str.length; i++) {
 index = str[i] - 'a'; // 获取当前字符的位置
 
 //当前下个字符位置如果为空 且 当前 节点不在根节点时，继续遍历cur节点的fail指针 直到遇到当前下个字符位置i不为空 或者cur 指向返回到了root节点 退出循环
 while (cur.nexts[index] == null && cur != root) {
 cur = cur.fail;
 }
 //刷新cur 当前来到的节点位置
 //如果是nexts指向不为空退出的情况 那么表示当前这个字符是存在前缀树结果中 接着指向下个字符 如果是cur指向到了root 说明就不存在该字符 那么就是返回root 节点
 cur = cur.nexts[index] != null ? cur.nexts[index] : root;
 //此时 将follow节点 指向cur节点 进行前缀树的遍历 判断其指向fail节点的end是否存在值 若是那么就表示该值字符串是包含在大文章字符串中的 添加到结果集
 //使得cur指向保持不变 对于下次遍历就从cur开始
 follow = cur;
 while (follow != root) {
 //遍历 直到回到root 就退出循环
 if (follow.endUse) {
 break; //先判断 当前节点是否是已经加入过了的字符串 如果是就直接退出循环 后续的就不用再继续指向了 因为已经加过了
 }
 
 if (follow.end != null) {
 res.add(follow.end); //如果end字符串非空 说明当前这个字符串包含在大文章中 添加到集合
 follow.endUse = true; //设置当前字符串已经加入集合 后续再遍历到的时候就可以直接退出 当然这句可以直接放在if外面执行 都是一样的 因为遍历过的当前fail指针节点都不需要下次再重复遍历
 }
 follow = follow.fail; //follow节点继续指向fail指针节点
 }
 }
 return res; //最后返回该集合
 
 }
 }
 
 public static void main(String[] args) {
 ACAutomation ac = new ACAutomation();
 ac.insert("dhe");
 ac.insert("he");
 ac.insert("abcdheks");
 // 设置fail指针
 ac.build();
 
 List<String> contains = ac.containWords("abcdhekskdjfafhasldkflskdjhwqaeruv");
 for (String word : contains) {
 System.out.println(word);
 }
 }
 
 }