c# 实现KMP算法的示例代码
作者:温暖如太阳 发布时间:2023-12-02 06:35:19
标签:c#,kmp,算法
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。
实现方式就不再这里献丑了,网上很多讲解,此处只是记录下c#实现的代码。
public class KMP
{
public static int[] GetNext(String ps)
{
char[] p = ps.ToArray();
int[] next = new int[p.Length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.Length - 1)
{
if (k == -1 || p[j] == p[k])
{
next[++j] = ++k;
}
else
{
k = next[k];
}
}
return next;
}
public static int GetIndex(String ts, String ps)
{
char[] t = ts.ToArray();
char[] p = ps.ToArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
int[] next = GetNext(ps);
while (i < t.Length && j < p.Length)
{
if (j == -1 || t[i] == p[j])
{
// 当j为-1时,要移动的是i,当然j也要归0
i++;
j++;
}
else
{
// i不需要回溯了
// i = i - j + 1;
j = next[j]; // j回到指定位置
}
}
if (j == p.Length)
{
return i - j;
}
else
{
return -1;
}
}
}
//test
static void Main(string[] args)
{
Console.WriteLine( KMP.GetIndex("abcdbcxdbc", "dbc"));
Console.ReadKey();
}
来源:https://www.cnblogs.com/xtt321/p/14022697.html
0
投稿
猜你喜欢
- 在开发中,我们会遇到将不同组织架构合并成tree这种树状结构,那么如果做呢?实际上,我们也可以理解为如何将拥有父子关系的list转成树形结构
- 一、什么是默认方法,为什么要有默认方法简单说,就是接口可以有实现方法,而且不需要实现类去实现其方法。只需在方法名前面加个default关键字
- 前言在开发过程中,会遇到很多的实体需要将查出的数据处理为下拉或者级联下拉的结构,提供给前端进行展示。在数据库查出的结构中,可能是集合<
- 本文实例为大家分享了Android实现悬浮窗效果的具体代码,供大家参考,具体内容如下一、权限:<uses-permission and
- 在我们平时写程序的时候,有些参数是经常改变的,而这种改变不是我们预知的。比如说我们开发了一个操作数据库的模块,在开发的时候我们连接本地的数据
- 一、save(单条添加)源码@Transactional@Overridepublic <S extends T> S save
- 1.数据数据(Data)是外部世界信息的载体, 是能够被计算机识别,加工,存储的。在现实生活中也就是我们的产品原材料。计算机中的数据包括数值
- 一、前言文稿扫描大家用的都比较频繁、想是各种证件、文件都可以通过扫描文稿功能保存到手机。相比直接拍照,在扫描文稿时,程序会对图像进行一些矫正
- java使用stream实现list中对象属性的合并:根据两个List中的某个相同字段合并成一条List,包含两个List中的字段一、前言为
- 概念代理:为控制A对象,而创建出新B对象,由B对象代替执行A对象所有操作,称之为代理。一个代理体系建立涉及到3个参与角色:真实对象(A),代
- using System;namespace Partial{ class Program { &nb
- Spring @Configuration 和 @Component 区别一句话概括就是 @Configuration 中所有带 @Bean
- Java深入到一定程度,就不可避免的碰到设计模式(design pattern)这一概念,了解设计模式,将使自己对java中的接口或抽象类应
- 1、 定义头和根元素部署描述符文件就像所有XML文件一样,必须以一个XML头开始。这个头声明可以使用的XML版本并给出文件的字符编码。DOC
- 一.static关键字使用场景static关键字主要有以下5个使用场景:1.1、静态变量把一个变量声明为静态变量通常基于以下三个目的:作为共
- throw抛出异常的方式比较直接:if(age < 0){throw new MyException("年龄不能为负数!&q
- @Autowired注入依赖失败的问题1、现象描述在Spring Boot项目中使用@Autowired注解,程序启动时发现服务启动失败,提
- 一、前言之前介绍了JMeter engine启动原理,但是里面涉及到HashTree这个类结构没有给大家详细介绍,这边文章就详细介绍JMet
- 缘起经过前面三章的入门,我们大概了解了Mybatis的主线逻辑是什么样子的,在本章中,我们将正式进入Mybatis的源码海洋。Mybatis
- 成为一个优秀的Java程序员,有着良好的代码编写习惯是必不可少的。下面就让我们来看看代码编写的30条建议吧。(1) 类名首字母应该大写。字段