首页 / 算法 / C#版泛型kmp算法

C#版泛型kmp算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C#版泛型kmp算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7992字，纯文字阅读大概需要12分钟。

内容图文

原文链接：http://www.cnblogs.com/zhy2002/archive/2008/04/01/1132639.html

#region KMP generic

        private static int[] Next(IList<T> pattern)
        {
            int[] next = new int[pattern.Count];
            next[0] = -1;
            if (pattern.Count < 2) //如果只有1个元素不用kmp效率会好一些
            {
                return next;
            }

            next[1] = 0;    //第二个元素的回溯函数值必然是0，可以证明：
            //1的前置序列集为{空集,L[0]}，L[0]的长度不小于1，所以淘汰，空集的长度为0，故回溯函数值为0
            int i = 2; //正被计算next值的字符的索引
            int j = 0; //计算next值所需要的中间变量，每一轮迭代初始时j总为next[i-1]
            while (i < pattern.Count)    //很明显当i==pattern.Length时所有字符的next值都已计算完毕，任务已经完成
            { //状态点
                //用Equals作为元素匹配条件
                if (pattern[i - 1].Equals(pattern[j]))   //首先必须记住在本函数实现中，迭代计算next值是从第三个元素开始的
                {   //如果L[i-1]等于L[j]，那么next[i] = j + 1
                    next[i++] = ++j;
                }
                else
                {   //如果不相等则检查next[i]的下一个可能值----next[j]
                    j = next[j];
                    if (j == -1)    //如果j == -1则表示next[i]的值是1
                    {   //可以把这一部分提取出来与外层判断合并
                        //书上的kmp代码很难理解的一个原因就是已经被优化，从而遮蔽了其实际逻辑
                        next[i++] = ++j;
                    }
                }
            }
            return next;

}

        public static int ExecuteKMP(IEnumerable<T> source, IList<T> pattern)
        {
            int[] next = Next(pattern);
            return ExecuteKMPInternal(source, pattern, next);
        }

        private static int ExecuteKMPInternal(IEnumerable<T> source, IList<T> pattern, int[] next)
        {
            IEnumerator<T> iterator = source.GetEnumerator();

int i = iterator.MoveNext() ? 0 : -1;//这两条语句必须总是一起执行 //主串指针

            int j = 0; //模式串指针
            //如果子串没有匹配完毕并且主串没有搜索完成
            while (j < pattern.Count && i > -1)
            {
                if (iterator.Current.Equals(pattern[j]))    //i和j的逻辑意义体现于此，用于指示本轮迭代中要判断是否相等的主串字符和模式串字符
                {
                    i = iterator.MoveNext() ? i + 1 : -1;
                    j++;
                }
                else
                {
                    j = next[j];    //依照指示迭代回溯
                    if (j == -1)    //回溯有情况，这是第二种
                    {
                        i = iterator.MoveNext() ? i + 1 : -1;
                        j++;
                    }
                }
            }
            //如果j==pattern.Length则表示循环的退出是由于子串已经匹配完毕而不是主串用尽
            return j < pattern.Count ? -1 : i - j;
        }

        /// <summary>
        /// 泛型版的Next函数
        /// </summary>
        /// <param name="pattern">模式串可以是一个实现了IList的对象，所有数组都实现了IList</param>
        /// <param name="isEqual">此函数必须是反映一个等价关系，即满足自反、传递、交换，否则算法会出现逻辑错误。这是KMP算法的前提。</param>
        /// <returns>返回Next回溯函数</returns>
        private static int[] Next(IList<T> pattern, Func<T, T, bool> isEqual)
        {
            int[] next = new int[pattern.Count];
            next[0] = -1;
            if (pattern.Count < 2) //如果只有1个元素不用kmp效率会好一些
            {
                return next;
            }

            next[1] = 0;    //第二个元素的回溯函数值必然是0，可以证明：
            //1的前置序列集为{空集,L[0]}，L[0]的长度不小于1，所以淘汰，空集的长度为0，故回溯函数值为0
            int i = 2; //正被计算next值的字符的索引
            int j = 0; //计算next值所需要的中间变量，每一轮迭代初始时j总为next[i-1]
            while (i < pattern.Count)    //很明显当i==pattern.Length时所有字符的next值都已计算完毕，任务已经完成
            { //状态点
                //用Equals作为元素匹配条件
                if (isEqual(pattern[i - 1], pattern[j]))   //首先必须记住在本函数实现中，迭代计算next值是从第三个元素开始的
                {   //如果L[i-1]等于L[j]，那么next[i] = j + 1
                    next[i++] = ++j;
                }
                else
                {   //如果不相等则检查next[i]的下一个可能值----next[j]
                    j = next[j];
                    if (j == -1)    //如果j == -1则表示next[i]的值是1
                    {   //可以把这一部分提取出来与外层判断合并
                        //书上的kmp代码很难理解的一个原因就是已经被优化，从而遮蔽了其实际逻辑
                        next[i++] = ++j;
                    }
                }
            }
            return next;

}

        public static int ExecuteKMP(IEnumerable<T> source, IList<T> pattern, Func<T, T, bool> isEqual)
        {
            int[] next = Next(pattern, isEqual);
            return ExecuteKMPInternal(source, pattern, isEqual, next);
        }

        private static int ExecuteKMPInternal(IEnumerable<T> source, IList<T> pattern, Func<T, T, bool> isEqual, int[] next)
        {
            IEnumerator<T> iterator = source.GetEnumerator();

int i = iterator.MoveNext() ? 0 : -1;//这两条语句必须总是一起执行 //主串指针

            int j = 0; //模式串指针
            //如果子串没有匹配完毕并且主串没有搜索完成
            while (j < pattern.Count && i > -1)
            {
                if (isEqual(iterator.Current, pattern[j]))    //i和j的逻辑意义体现于此，用于指示本轮迭代中要判断是否相等的主串字符和模式串字符
                {
                    i = iterator.MoveNext() ? i + 1 : -1;

                    j++;
                }
                else
                {
                    j = next[j];    //依照指示迭代回溯
                    if (j == -1)    //回溯有情况，这是第二种
                    {
                        i = iterator.MoveNext() ? i + 1 : -1;
                        j++;
                    }
                }
            }
            //如果j==pattern.Length则表示循环的退出是由于子串已经匹配完毕而不是主串用尽
            return j < pattern.Count ? -1 : i - j;
        }

        private static int[] NextVal(IList<T> pattern)
        {
            int[] next = new int[pattern.Count];
            next[0] = -1;
            if (pattern.Count < 2) //如果只有1个元素不用kmp效率会好一些
            {
                return next;
            }

            next[1] = 0;    //第二个元素的回溯函数值必然是0，可以证明：
            //1的前置序列集为{空集,L[0]}，L[0]的长度不小于1，所以淘汰，空集的长度为0，故回溯函数值为0
            int i = 2; //正被计算next值的字符的索引
            int j = 0; //计算next值所需要的中间变量，每一轮迭代初始时j总为next[i-1]
            while (i < pattern.Count)    //很明显当i==pattern.Length时所有字符的next值都已计算完毕，任务已经完成
            { //状态点
                //用Equals作为元素匹配条件
                if (j == -1 || pattern[i - 1].Equals(pattern[j]))   //首先必须记住在本函数实现中，迭代计算next值是从第三个元素开始的
                {   //如果L[i-1]等于L[j]，那么next[i] = j + 1
                    j++;
                    if (pattern[i].Equals(pattern[j]))
                    {
                        next[i] = next[j];
                    }
                    else
                    {
                        next[i] = j;
                    }
                    i++;
                }
                else
                {   //如果不相等则检查next[i]的下一个可能值----next[j]
                    j = next[j];
                }
            }
            return next;
        }

        public static int ExecuteKMPP(IEnumerable<T> source, IList<T> pattern)
        {
            int[] next = NextVal(pattern);
            return ExecuteKMPInternal(source, pattern, next);
        }

#endregion

刚才测试一下，貌似没有问题。

转载于:https://www.cnblogs.com/zhy2002/archive/2008/04/01/1132639.html

内容总结

以上是互联网集市为您收集整理的C#版泛型kmp算法全部内容，希望文章能够帮你解决C#版泛型kmp算法所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/754654.html

来源：【匿名】

【上一篇】ros中开发rnnoise语音增强算法的开发示例【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【C#版泛型kmp算法】教程文章相关的互联网学习教程文章

泛型算法（四）之计数算法【代码】

1、count(InputIterator first, InputIterator last, const T& val)：序列中等于给定值的元素的计数 std::vector<int> c;c.reserve(10);//向c中添加元素for (int i = 0; i < 10; i++){c.push_back(i * 0);}//计算c中元素值等于0的元素个数int count = std::count(c.begin(), c.end(), 0);//输出std::cout << count;//打印结果：102、count_if(InputIterator first, InputIterator last, UnaryPredicate pred)：序列中满足给定谓...

算法学习之基础(背包列队栈) 习题1.3.33泛型双向队列【代码】

前几天写的。。 1package gh;2 3import java.util.Iterator;4 5/** 6 * 泛型双向队列（双向链表实现）7 * @author ganhang8 *9*/ 10publicclass Deque<T> implements Iterable<T> {11private Node first;12private Node last;13privateint n=0;14public Deque(){15 16 }17//从左边加入 18publicvoid pushLeft(T item) {19if (first == null) {20 first=new Node(item); 21 last=first;22 ...

第十一章泛型算法 C++ PRIMER

vector<int>::const_iterator result = find(vector.begin(). vector.end(),search_value); 如果查找失败，分会end（）如果有两个，会返回哪一个的迭代器？int *reauslt = find(ia,ia+6,search_value); 也可以同样处理字符串算法要以<algorithm><numeric>,依赖于迭代器和迭代器的算法实现，算法可能改变值，可能移动元素，单从不直接添加或者删除元素int sum = accumulate(vec.begin(),vec.end(),42); 最后一个参数是必须的，因...

黑马程序员——17，集合，TreeSet，二叉树，泛型

------<ahref="http://www.itheima.com" target="blank">Java培训、Android培训、iOS培训、.Net培训</a>、期待与您交流！ ------- 黑马程序员——17，集合，TreeSet，二叉树，泛型 /* TreeSet:可以自动对容器内部元素排序*/import java.util.*; //Collection接口的体系放在Java.util包里面class Jihe13 {publicstatic void main(String[] args){method();}public static void method(){soc("下...

[算法与数据结构]使用Java泛型实现栈【代码】

题解1 实现内部类node 2 维护top为头节点的链表 3 操作操作1：push() 操作2: pop() 操作3: isEmpty()代码package Exam;class MyStackStruct<T> {private class Node<U> {U val;Node<U> next;Node() {this.val = null;this.next = null;}Node(U val, Node<U> next) {this.val = val;this.next = next;}boolean isEmptyNode() {return this.val == null && this.next == null;}}private Node<T> top = new Node<>();public void p...

C++ STL标准库常用泛型算法【代码】

转自：https://www.cnblogs.com/wkfvawl/p/9475939.html，https://www.cnblogs.com/linuxAndMcu/p/10264339.html1.二分查找#include <algorithm>//查找某个元素是否出现，返回布尔类型，找到value返回1，否则返回0，并不会返回下标 binary_search(arr[],arr[]+size ,value)//在数组中 binary_search(a.begin(),a.end(),value)//在向量中//查找第一个大于等于某个值的迭代器，返回对应容器类型的iterator lower_bound(arr[],arr[]+s...

C++研发泛型编程第十七讲【常用拷贝和替换算法】【代码】

一、copy 功能描述：容器内指定范围的元素拷贝到另一容器中函数原型：copy(iterator beg, iterator end, iterator dest); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // dest 目标起始迭代器示例： #include <algorithm> #include <vector>class myPrint { public:void operator()(int val){cout << val << " ";} };void test01() {vector<int> v1;for (int i =...

C++ Primer 5th笔记（10）chapter10 泛型算法：泛型算法结构【代码】

名称定义输入迭代器只读，不写；单遍扫描，只能递增输出迭代器只写，不读；单遍扫描，只能递增前向迭代器可读写，多遍扫描，只能递增双向迭代器可读写，多遍扫描，可递增递减随机访问迭代器可读写，多遍扫描，支持全部迭代器运算1. 输入迭代器(input iterator) 支持的操作集：==, !=, 前缀++, 后缀++, *, ->。 eg1. istream_iterator是一种输入迭代器 eg2. find, accumulate算法要求输入迭代器 find(line.crbegin(), line.crend(),...

C++中泛型算法详解2：lambda表达式【图】

前言上一节关于泛型算法的介绍中，我们使用过sort排序算法，仅仅传入了vector的开头和结尾的两个迭代器。该算法还会接受第三个参数：谓词参数(predicate) 谓词是一个可调用的表达式，返回一个能用做条件的值。所有的标准库使用的谓词分为两类：一元谓词（单一参数）二元谓词（两个参数）介绍lambda 一个lambda表示一个可调用代码单元。我们可以把它理解为一个未命名的内敛函数。形式如下： [capture list] (parameter list) -...

C++中泛型算法详解1：只读算法、读写算法、重排容器元素的算法【代码】

简介标准库提供了超过100个算法，这些算法有一致的结构。理解这些算法的基本方法是了解他们是否读取元素、改变元素或者重排元素顺序。泛型算法特点：算法不依赖容器所保存的元素类型。只要有迭代器能够访问元素即可。大多数算法都会使用一个或多个元素上的操作，通常，我们可以使用自定义的操作来代替默认的运算符。算法本身永远不会执行容器上的操作，只是运行在迭代器上，执行迭代器的操作。 1. 只读算法 // findvector<int...

泛型算法：拷贝算法copy()【代码】【图】

struct ceshi {int frist = 0;int second = 0; };int main(int argc, char *argv[]) {QList<ceshi> list;ceshi c1;c1.frist = 1;c1.second = 2;ceshi c2;c2.frist = 3;c2.second = 4;list << c1 << c2;std::list<ceshi> list2;list2.resize(list.size());auto ret = std::copy(std::begin(list),std::end(list),std::begin(list2));for (auto it = list2.begin();it != list2.end();++it){qDebug()<<it->frist<<it->second;} }其中...

STL-泛型算法（lambda、bind、多种迭代器）

C++ PRIMER 10 本章主要内容有lambda、bind和多种迭代器。 lambda和bind都应用于定制操作。谓词：是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：一元谓词（只接受单一参数）和二元谓词（有两个参数）如函数指针作为参数时，调用过程中，可用其指向的函数计算。。 1）lambda：匿名函数我们可以向一个算法传递任何类别的可调用对象。函数和函数指针就是可调用对象。还有function和lam...

C++泛型冒泡排序代码【代码】

文件： // File: bubbleSort.h #ifndef _BUBBLESORT_H_ #define _BUBBLESORT_H_template <typename numeric>void bubbleSort(numeric* arr, int size, int direction) {if (!direction)return;else {direction = (direction < 0) ? -1 : 1;numeric temp;for (int i = 0; i < size-1; i++) {for (numeric* j = arr; j < arr+size-i-1; j++) {if (*j*direction > *(j+1)*direction) {temp = *j;*j = *(j+1);*(j+1) = temp;}}}return;...