C#,字符串匹配(模式搜索)AC(Aho Corasick)算法的源代码
Aho-Corasick算法简称AC算法,也称为AC自动机(Aho-Corasick)算法,1975年产生于贝尔实验室(The Bell Labs),是一种用于解决多模式字符串匹配的经典算法之一。

the Bell Lab
本文的运行效果:

AC算法以模式树(字典树)Trie、广度优先策略和KMP模式匹配算法为核心内容。
using System;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
/// <summary>
/// Aho_Corasick 算法
/// </summary>
public static partial class PatternSearch
{
private static int MAXS = 512;
private static int MAXC = 26;
private static int[] outt = new int[MAXS];
private static int[] f = new int[MAXS];
private static int[,] g = new int[MAXS, MAXC];
private static int buildMatchingMachine(string[] arr, int k)
{
for (int i = 0; i < outt.Length; i++)
{
outt[i] = 0;
}
for (int i = 0; i < MAXS; i++)
{
for (int j = 0; j < MAXC; j++)
{
g[i, j] = -1;
}
}
int states = 1;
for (int i = 0; i < k; ++i)
{
string word = arr[i];
int currentState = 0;
for (int j = 0; j < word.Length; ++j)
{
int ch = word[j] - 'A';
if (g[currentState, ch] == -1)
{
g[currentState, ch] = states++;
}
currentState = g[currentState, ch];
}
outt[currentState] |= (1 << i);
}
for (int ch = 0; ch < MAXC; ++ch)
{
if (g[0, ch] == -1)
{
g[0, ch] = 0;
}
}
for (int i = 0; i < MAXC; i++)
{
f[i] = 0;
}
Queue<int> q = new Queue<int>();
for (int ch = 0; ch < MAXC; ++ch)
{
if (g[0, ch] != 0)
{
f[g[0, ch]] = 0;
q.Enqueue(g[0, ch]);
}
}
while (q.Count != 0)
{
int state = q.Peek();
q.Dequeue();
for (int ch = 0; ch < MAXC; ++ch)
{
if (g[state, ch] != -1)
{
int failure = f[state];
while (g[failure, ch] == -1)
{
failure = f[failure];
}
failure = g[failure, ch];
f[g[state, ch]] = failure;
outt[g[state, ch]] |= outt[failure];
q.Enqueue(g[state, ch]);
}
}
}
return states;
}
private static int findNextState(int currentState, char nextInput)
{
int answer = currentState;
int ch = nextInput - 'A';
while (g[answer, ch] == -1)
{
answer = f[answer];
}
return g[answer, ch];
}
public static List<int> Aho_Corasick_Search(string text, string pattern, int k = 1)
{
List<int> matchs = new List<int>();
string[] arr = new string[1] { pattern };
buildMatchingMachine(arr, k);
int currentState = 0;
for (int i = 0; i < text.Length; ++i)
{
currentState = findNextState(currentState, text[i]);
if (outt[currentState] == 0)
{
continue;
}
for (int j = 0; j < k; ++j)
{
if ((outt[currentState] & (1 << j)) > 0)
{
matchs.Add((i - arr[j].Length + 1));
}
}
}
return matchs;
}
}
}
POWER BY TRUFFER.CN
using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{/// <summary>/// Aho_Corasick 算法/// </summary>public static partial class PatternSearch{private static int MAXS = 512;private static int MAXC = 26;private static int[] outt = new int[MAXS];private static int[] f = new int[MAXS];private static int[,] g = new int[MAXS, MAXC];private static int buildMatchingMachine(string[] arr, int k){for (int i = 0; i < outt.Length; i++){outt[i] = 0;}for (int i = 0; i < MAXS; i++){for (int j = 0; j < MAXC; j++){g[i, j] = -1;}}int states = 1;for (int i = 0; i < k; ++i){string word = arr[i];int currentState = 0;for (int j = 0; j < word.Length; ++j){int ch = word[j] - 'A';if (g[currentState, ch] == -1){g[currentState, ch] = states++;}currentState = g[currentState, ch];}outt[currentState] |= (1 << i);}for (int ch = 0; ch < MAXC; ++ch){if (g[0, ch] == -1){g[0, ch] = 0;}}for (int i = 0; i < MAXC; i++){f[i] = 0;}Queue<int> q = new Queue<int>();for (int ch = 0; ch < MAXC; ++ch){if (g[0, ch] != 0){f[g[0, ch]] = 0;q.Enqueue(g[0, ch]);}}while (q.Count != 0){int state = q.Peek();q.Dequeue();for (int ch = 0; ch < MAXC; ++ch){if (g[state, ch] != -1){int failure = f[state];while (g[failure, ch] == -1){failure = f[failure];}failure = g[failure, ch];f[g[state, ch]] = failure;outt[g[state, ch]] |= outt[failure];q.Enqueue(g[state, ch]);}}}return states;}private static int findNextState(int currentState, char nextInput){int answer = currentState;int ch = nextInput - 'A';while (g[answer, ch] == -1){answer = f[answer];}return g[answer, ch];}public static List<int> Aho_Corasick_Search(string text, string pattern, int k = 1){List<int> matchs = new List<int>();string[] arr = new string[1] { pattern };buildMatchingMachine(arr, k);int currentState = 0;for (int i = 0; i < text.Length; ++i){currentState = findNextState(currentState, text[i]);if (outt[currentState] == 0){continue;}for (int j = 0; j < k; ++j){if ((outt[currentState] & (1 << j)) > 0){matchs.Add((i - arr[j].Length + 1));}}}return matchs;}}
}
相关文章:
C#,字符串匹配(模式搜索)AC(Aho Corasick)算法的源代码
Aho-Corasick算法简称AC算法,也称为AC自动机(Aho-Corasick)算法,1975年产生于贝尔实验室(The Bell Labs),是一种用于解决多模式字符串匹配的经典算法之一。 the Bell Lab 本文的运行效果: AC算法以模式树…...
【网络取证篇】Windows终端无法使用ping命令解决方法
【网络取证篇】Windows终端无法使用ping命令解决方法 以Ping命令为例,最近遇到ping命令无法使用的情况,很多情况都是操作系统"环境变量"被改变或没有正确配置导致—【蘇小沐】 目录 1、实验环境(一)无法ping命令 &a…...
electron+vue网页直接播放RTSP视频流?
目前大部分摄像头都支持RTSP协议,但是在浏览器限制,最新版的浏览器都不能直接播放RTSP协议,Electron 桌面应用是基于 Chromium 内核的,所以也不能直接播放RTSP,但是我们又有这个需求怎么办呢? 市场上的方案…...
【Delphi 基础知识 19】Assigned的用法
在Delphi中,Assigned 是一个用于检查指针是否已分配内存的函数。它通常用于检查对象或指针是否已经被分配内存,以避免在未分配内存的情况下引用或操作它。 以下是 Assigned 的一些用法示例: 检查对象是否已分配内存: varMyObject…...
多线程在编程中的重要性有什么?并以LabVIEW为例进行说明
多线程在编程中的重要性体现在以下几个方面: 并行处理: 多线程允许程序同时执行多个任务,这在现代多核心处理器上尤其重要。通过并行处理,可以显著提高程序的执行效率和响应速度。 资源利用最大化: 通过多线程&#x…...
K8S---kubectl top
一、简介 该命令类似于linux–top命令,用于显示node和pod的CPU和内存使用情况 二、命令行 1、help命令 k top --help Display resource (CPU/memory) usage. The top command allows you to see the resource consumption for nodes or pods. This command requires Metri…...
Linux部署前后端项目
部署SpringBoot项目 创建SpringBoot项目 先确保有一个可以运行的springboot项目,这里就记录创建项目的流程了,可以自行百度。 命令行启动 2.1、在linux中,我是在data目录下新创建的一个project目录(此目录创建位置不限制&…...
一文搞懂系列——Linux C线程池技术
背景 最近在走读诊断项目代码时,发现其用到了线程池技术,感觉耳目一新。以前基本只是听过线程池,但是并没有实际应用。对它有一丝的好奇,于是趁这个机会深入了解一下线程池的实现原理。 线程池的优点 线程池出现的背景…...
stable diffusion代码学习笔记
前言:本文没有太多公式推理,只有一些简单的公式,以及公式和代码的对应关系。本文仅做个人学习笔记,如有理解错误的地方,请指出。 本文包含stable diffusion入门文献和不同版本的代码。 文献资源 本文学习的代码&…...
腾讯云服务器怎么买?两种购买方式更省钱
腾讯云服务器购买流程很简单,有两种购买方式,直接在官方活动上购买比较划算,在云服务器CVM或轻量应用服务器页面自定义购买价格比较贵,但是自定义购买云服务器CPU内存带宽配置选择范围广,活动上购买只能选择固定的活动…...
基于SpringBoot自定义控制是否需要开启定时功能
在基于SpringBoot的开发过程中,有时候会在应用中使用定时任务,然后服务器上启动定时任务,本地就不需要开启定时任务,使用一个参数进行控制,通过查资料得知非常简单。 参数配置 在application-dev.yml中加入如下配置 …...
“确定要在不复制其属性的情况下复制此文件?”解决方案(将U盘格式由FAT格式转换为NTFS格式)
文章目录 1.问题描述2.问题分析3.问题解决3.1 方法一3.2 方法二3.3 方法三 1.问题描述 从电脑上复制文件到U盘里会出现“确定要在不复制其属性的情况下复制此文件?”提示。 2.问题分析 如果这个文件在NTFS分区上,且存在特殊的安全属性。那么把它从NT…...
视频监控系统EasyCVR如何通过调用API接口查询和下载设备录像?
智慧安防平台EasyCVR是基于各种IP流媒体协议传输的视频汇聚和融合管理平台。视频流媒体服务器EasyCVR采用了开放式的网络结构,支持高清视频的接入和传输、分发,平台提供实时远程视频监控、视频录像、录像回放与存储、告警、语音对讲、云台控制、平台级联…...
15.鸿蒙HarmonyOS App(JAVA)进度条与圆形进度条
15.鸿蒙HarmonyOS App(JAVA)进度条与圆形进度条 progressBar2.setIndeterminate(true);//设置无限模式,运行查看动态效果 //创建并设置无限模式元素 ShapeElement element new ShapeElement(); element.setBounds(0,0,50,50); element.setRgbColor(new RgbColor(255,0,0)); …...
【FastAPI】路径参数
路径参数 from fastapi import FastAPIapp FastAPI()app.get("/items/{item_id}") async def read_item(item_id):return {"item_id": item_id}其中{item_id}就为路径参数 运行以上程序当访问 :http://127.0.0.1:8000/items/fastapi时候 将会…...
【docker笔记】DockerFile
DockerFile Docker镜像结构的分层 镜像不是一个单一的文件,而是有多层构成。 容器其实是在镜像的最上面加了一层读写层,在运行容器里做的任何文件改动,都会写到这个读写层。 如果删除了容器,也就是删除了其最上面的读写层&…...
React项目搭建流程
第一步 利用脚手架创建ts类型的react项目: 执行如下的命令:create-react-app myDemo --template typescript ; 第二步 清理项目目录结构: src/ index.tsx, app.txs, react-app-env.d.ts public/index.ht…...
QT DAY1作业
1.QQ登录界面 头文件代码 #ifndef MYWIDGET_H #define MYWIDGET_H#include <QWidget> #include <QIcon> #include <QLabel> #include <QPushButton> #include <QMovie> #include <QLineEdit>class MyWidget : public QWidget {Q_OBJECTpu…...
Java后端开发——Mybatis实验
文章目录 Java后端开发——Mybatis实验一、MyBatis入门程序1.创建工程2.引入相关依赖3.数据库准备4.编写数据库连接信息配置文件5.创建POJO实体6.编写核心配置文件和映射文件 二、MyBatis案例:员工管理系统1.在mybatis数据库中创建employee表2.创建持久化类Employee…...
【UE Niagara 网格体粒子系列】02-自定义网格
目录 步骤 一、创建自定义网格体 二、创建Niagara系统 步骤 一、创建自定义网格体 1. 打开Blender,按下ShiftA来创建一个平面 将该平面旋转90 导出为fbx 设置导出选定的物体,这里命名为“SM_PlaneFaceCamera.fbx” 按H隐藏刚才创建的平面&#x…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
