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();
}

以上就是c# 实现KMP算法的示例代码的详细内容，更多关于c# kmp算法的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C# 数独求解算法的实现

    前言 数独是一种有趣的智力游戏,但是部分高难度数独在求解过程中经常出现大量单元格有多个候选数字可以填入,不得不尝试填写某个数字然后继续推导的方法.不幸的是这种方法经常出现填到一半才发现有单元格无数可填,说明之前就有单元格填错了把后面的路堵死了.这时就需要悔步,之前的单元格换个数重新试.然而更坑的是究竟要悔多少步呢?不知道.要换数字的时候该换哪个呢?也不知道.手算时就需要大量草稿纸记录填写情况,不然容易忘了哪些试过哪些没试过. 在朋友那里玩他手机上的数独的时候就发现这个问题很烦,到这里其实就不是一

  • C#字符串自增自减算法详解

    C#实现字符串自增和自减运算,供大家参考,具体内容如下 1.数字从 0-9 变化: 2.字母从 A-Z.a-z 变化: 3.其它字符跳过: 4.以上变化依据其Ascii码值: /// <summary> /// 字符串运算 /// </summary> public class StringOperation { /// <summary> /// 通过ASCII码值,对字符串自增1 /// </summary> /// <param name=&qu

  • 同时兼容JS和C#的RSA加密解密算法详解（对web提交的数据加密传输）

    同时兼容JS和C#的RSA加密解密算法详解（对web提交的数据加密传输）

    前言 我们在Web应用中往往涉及到敏感的数据,由于HTTP协议以明文的形式与服务器进行交互,因此可以通过截获请求的数据包进行分析来盗取有用的信息.虽然https可以对传输的数据进行加密,但是必须要申请证书(一般都是收费的),成本较高.那么问题来了,如果对web提交的敏感数据进行加密呢?web应用中,前端的数据处理和交互基本上都是靠javascript来完成,后台的逻辑处理可以C#(java)等进行处理. 微软的C#中虽然有RSA算法,但是格式和OpenSSL生成的公钥/私钥文件格式并不兼容.这个

  • C#深度优先搜索算法

    本文实例为大家分享了C#深度优先搜索算法的具体代码,供大家参考,具体内容如下 //论文要用到其改进算法,在此先demo测试一下 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace DFS { class Program { public int[,] map = new int[100, 100];

  • C#实现简单的RSA非对称加密算法示例

    C#实现简单的RSA非对称加密算法示例

    本文实例讲述了C#实现简单的RSA非对称加密算法.分享给大家供大家参考,具体如下: 界面控件 namespace RSA算法 { partial class Form1 { /// <summary> /// 必需的设计器变量. /// </summary> private System.ComponentModel.IContainer components = null; /// <summary> /// 清理所有正在使用的资源. /// </summary

  • C#实现拼手气红包算法

    本文实例为大家分享了C#实现拼手气红包算法的具体代码,供大家参考,具体内容如下 一.方案1:即开即中,考虑机会均等,减少金额差较大的几率 可以每次点击时候,随机产生 static double[] GetRandomMoney(double money, int n) { double[] array = new double[n]; RedPackage red = new RedPackage() { money = money, count = n }; for (int i = 0; i

  • 经典实例讲解C#递归算法

    一 .递归算法简介 在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法. 递归算法是一种直接或者间接地调用自身算法的过程.在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解. 递归算法解决问题的特点: (1) 递归就是在过程或函数里调用自身. (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口. (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低.所以一般不提倡用递归算法设计程序. (4) 在递归调用的过程当中

  • 少见的C# RSA算法

    当下最流行的RSA加密算法,只有公钥和私钥同时拥有才能破解加密信息,RSA加密算法的出现有利于数据安全性传输 1.C#中自带RSACryptoServiceProvider类可以让你很好的生成XML格式的公钥和私钥,两句代码就搞定 2.但是生成的XML格式前端不能很好的利用和读懂,所以在生成的XML格式里需要转换成PEM格式,这样才能直接Copy到验证工具里加密解密,非常方便 首先,我们先导入一个第三方库,因为下面涉及到的转换代码都是需要依赖这个库来实现,导入操作如下 控制台里输入 PM > I

  • C#实现的二维数组排序算法示例

    本文实例讲述了C#实现的二维数组排序算法.分享给大家供大家参考,具体如下: class Order { /// <summary> /// 对二维数组排序 /// </summary> /// <param name="values">排序的二维数组</param> /// <param name="orderColumnsIndexs">排序根据的列的索引号数组</param> /// <

  • c# 实现位图算法（BitMap）

    算法原理 BitMap的基本思想就是用一个bit位来标记某个元素对应的Value,而Key即是该元素.由于采用了Bit为单位来存储数据,因此可以大大节省存储空间. BitMap可以看成一种数据结构. 假设有这样一个需求:在20亿个随机整数中找出某个数m是否存在其中,并假设32位操作系统,4G内存. 在Java中,int占4字节,1字节=8位(1 byte = 8 bit). 如果每个数字用int存储,那就是20亿个int,因而占用的空间约为 (2000000000*4/1024/1024/102

  • 使用C#编写自己的区块链挖矿算法

    什么是加密货币挖掘? 一个加密货币的价值体现在它的稀缺性上,如果任何人都可以任意构造一个比特币,那么比特币就毫无价值,所以比特币的区块链会让参与者完成一项"工作",根据这个工作的最终结果还分发比特币,这个过程就被叫做"挖矿".这就类似于一个黄金矿工花一些时间来工作,然后获得一点黄金. 挖矿的原理 如果你百度/谷歌搜索 比特币挖矿的原理 的话,都会给你说是计算一个复杂的数学问题而已,但是这么说的话太笼统而且也太简单.采矿引擎如何工作这是一个重要的知识点,所以我们需要了

  • KMP算法的C#实现方法

    本文实例简述了KMP算法的C#实现方法,分享给大家供大家参考.具体如下: 具体思路为:next函数求出模式串向右滑动位数,再将模式串的str的next函数值 存入数组next. 具体实现代码如下: static void GetNextVal(string str, int [] next) { int i = 0; int j = -1; next[0] = -1; while (i < str.Length - 1) { if (j == -1 || str[i] == str[j]) {

随机推荐