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…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
