C#,字符串匹配(模式搜索)Sunday算法的源代码
2023-09-11 14:15:48 时间
Sunday算法是Daniel M.Sunday于1990年提出的一种字符串模式匹配算法。
核心思想:在匹配过程中,模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较,它在发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。
Sunday算法思想跟BM(Boyer Moore)算法很相似,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过,即:移动步长=匹配串长度+1;否则,同BM算法一样,其移动步长=匹配串中最右端的该字符到末尾的距离+1。
本代码运行效果:
源代码:
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
public static partial class PatternSearch
{
/// <summary>
/// 字符位置表
/// </summary>
private static int ALPHA_BET = 512;
/// <summary>
/// 计算字符的出现位置表
/// </summary>
/// <param name="pattern"></param>
/// <returns></returns>
private static int[] ComputeOccurence(string pattern)
{
int[] table = new int[ALPHA_BET];
for (char a = (char)0; a < (char)ALPHA_BET; a++)
{
table[(int)a] = -1;
}
for (int i = 0; i < pattern.Length; i++)
{
char a = pattern[i];
table[(int)a] = i;
}
return table;
}
/// <summary>
/// 字符串匹配算法(模式搜索)Sunday算法
/// </summary>
/// <param name="text"></param>
/// <param name="pattern"></param>
/// <returns></returns>
public static List<int> Sunday_Search(string text, string pattern)
{
List<int> matchs = new List<int>();
int i = 0;
int[] table = ComputeOccurence(pattern);
while (i <= text.Length - pattern.Length)
{
int j = 0;
while (j < pattern.Length && text[i + j] == pattern[j])
{
j++;
}
if (j == pattern.Length)
{
matchs.Add(i);
}
i += pattern.Length;
if (i < text.Length)
{
i -= table[(int)text[i]];
}
}
return matchs;
}
}
}
——————————————————————
POWER BY 315SOFT.COM &
TRUFFER.CN
相关文章
- C#winform抓取百度,Google搜索关键词结果
- C# DateTime的11种构造函数 [Abp 源码分析]十五、自动审计记录 .Net 登陆的时候添加验证码 使用Topshelf开发Windows服务、记录日志 日常杂记——C#验证码 c#_生成图片式验证码 C# 利用SharpZipLib生成压缩包 Sql2012如何将远程服务器数据库及表、表结构、表数据导入本地数据库
- 利用反射快速给Model实体赋值 使用 Task 简化异步编程 Guid ToString 格式知多少?(GUID 格式) Parallel Programming-实现并行操作的流水线(生产者、消费者) c# 无损高质量压缩图片代码 8种主要排序算法的C#实现 (一) 8种主要排序算法的C#实现 (二)
- 常量,字段,构造方法 调试 ms 源代码 一个C#二维码图片识别的Demo 近期ASP.NET问题汇总及对应的解决办法 c# chart控件柱状图,改变柱子宽度 使用C#创建Windows服务 C#服务端判断客户端socket是否已断开的方法 线程 线程池 Task .NET 单元测试的利剑——模拟框架Moq
- C#不用union,而是有更好的方式实现 .net自定义错误页面实现 .net自定义错误页面实现升级篇 .net捕捉全局未处理异常的3种方式 一款很不错的FLASH时种插件 关于c#中委托使用小结 WEB网站常见受攻击方式及解决办法 判断URL是否存在 提升高并发量服务器性能解决思路
- C#编译器优化那点事 c# 如果一个对象的值为null,那么它调用扩展方法时为甚么不报错 webAPI 控制器(Controller)太多怎么办? .NET MVC项目设置包含Areas中的页面为默认启动页 (五)Net Core使用静态文件 学习ASP.NET Core Razor 编程系列八——并发处理
- 浅谈c#的三个高级参数ref out 和Params C#中is与as的区别分析 “登陆”与“登录”有何区别 经典SQL语句大全(绝对的经典)
- 浅谈JS中的!=、== 、!==、===的用法和区别 JS中Null与Undefined的区别 读取XML文件 获取路径的方式 C#中Cookie,Session,Application的用法与区别? c#反射 抽象工厂
- C#,铁蛋·奥纳奇数(Geek Onacci Number)的算法与源代码
- C#,深度优先搜索(DFS)、广度优先搜索(BFS)算法的源代码与数据可视化
- C#,初学琼林(05)——二分法查找(binary search,二分法搜索)数组内指定值的算法与源代码
- UDP Sockets in C#
- C# MVC @Html.DropDownListFor对简单的下拉列表的匿名类构造方法
- 【C#基础1-9】C#的面向对象三大特性
- 《C#零基础入门之百识百例》(四十五)类的属性 -- 单例模式
- 【C#】List列表的深复制,引用类型深复制
- C#判断网站是否能访问或者宕机的方法