精华内容
下载资源
问答
  • 数据结构 串模式匹配 KMP算法

    千次阅读 2019-03-13 21:23:26
    数据结构 KMP算法实现 KMP算法应用于模式匹配中 普通模式匹配算法在进行匹配时需要频繁对主指针进行回溯,KMP算法通过将模式向右滑动一段距离的方式避免了主的回溯,同时降低了算法复杂度 ,由...

    【数据结构】 串 KMP算法实现


    KMP算法应用于串的模式匹配中


    普通模式匹配算法在进行匹配时需要频繁对主串指针进行回溯,KMP算法通过将模式向右滑动一段距离的方式避免了主串的回溯,同时降低了算法复杂度 ,由原来的O(n*m)变为O(n)。

    KMP算法本身比较容易理解,就是对模式串本身的结构进行分析,在匹配过程中跳过一些不必要的步骤。
    比如当模式串为ababc; 主串为ababdddd时; 匹配进行到第五个字符处时失败了,但是这时主串指针不必进行回退(又重新从第二个字符b处开始比较),只需要根据模式串的 nest 函数,将模式指针进行移动,再进行下一次判断。
    在这里插入图片描述


    next函数求解

    KMP算法难以理解的点在于 next 函数的求解
    要弄明白一些基本的东西:
    在比较的过程中,存在着两个指针,

    1. 主串指针,指向当前主串正在进行比较的字符
    2. 模式串指针,指向模当前正在匹配的模式串的字符位置
      在使用KMP算法时,主串是不会进行回溯的,只有右移操作,主要是对模式串指针的滑动操作。

    算了,写不下去了

    弄懂之后才知道为什么书上写得那么晦涩难懂了。因为实在是很难说明白

    1.递推

    2.这个问题可以看成一个模式匹配问题,整个模式串既是主串,又是模式串。

    3.在求解 next【n+1】的过程中,其实还是在进行模式匹配,可以通过已知的next来获得next【n+1】

    4.后面的优化:对于 第 j 个字符 ,如果与next [ j ]所指示的字符相等,那么 next [ j ] = next [ next[j] ].


    想要理解整个算法,建议自己照着书上的思路走一遍,写一遍代码,模拟整个函数的执行过程,差不多懂了之后再回过头看看定义 (网上很多详解都没有把整个思路讲清,还得自己悟)

    代码部分:

    下面是KMP算法的实现,代码中串采用堆分配存储表示,书中串的存储方式为定长顺序串,代码略有区别

    1.采用KMP算法的模式匹配函数
    int Index_KMP(HString S, HString T, int pos,int next[]) {
    	//利用模式串T的next函数求T在主串中第pos个字符之后的位置的KMP算法。
    	int i = pos;
    	int j = 0;
    	while (i<S.length&&j<T.length)
    	{
    		if (j == -1 || S.ch[i] == T.ch[j]) { ++i; ++j; }
    		else
    		{
    			j = next[j];
    		}
    	}
    	if (j >= T.length)return i - T.length+1;	//匹配成功
    	else return -1;								//输出-1失败
    }
    

    2.KMP算法中next函数求取过程

    void get_next(HString T, int next[]) {
    	//求模式串T的next函数值并存入数组next
    	int i = 0; next[0] = -1; int j = -1;
    	while (i < T.length-1) {
    		if (j == -1 || T.ch[i] == T.ch[j]) { ++i; ++j; next[i] = j; }
    		else
    		{
    			j = next[j];
    		}
    	}
    	//get_next
    }
    

    3.next函数求取优化

    void get_nextval(HString T, int nextval[]) {
    	int i = 0; nextval[0] = -1; int j = -1;
    	while (i < T.length - 1) {
    		if (j == -1 || T.ch[i] == T.ch[j]) { 
    			++i; ++j;
    			if (T.ch[i] != T.ch[j])nextval[i] = j;
    			else nextval[i] = nextval[j];
    		}
    		else
    		{
    			j = nextval[j];
    		}
    	}
    	//get_nextval
    }
    

    4.测试部分

    #include"String.h"
    #include"KMP.h"
    using namespace std;
    
    void StrDisplay(HString S) {
    	//显示串
    	for (int i = 0; i < S.length; i++)
    	{
    		cout << S.ch[i];
    	}
    }
    int main() {
    	HString A;
    	StrInit(A);
    	HString B;
    	StrInit(B);
    	HString C;
    	StrInit(C);
    	char b[20] = "ababbbabaabcaccc";
    	char c[10] = "abaabcac";
    	int next[10] = { -1,0,0,1,1,2,0,1 };
    	cout << "初始化B,显示B:" << endl;
    	StrAssigh(B, b);
    	StrDisplay(B);
    
    	cout << endl<<"初始化C,显示C:" << endl;
    	StrAssigh(C, c);
    	StrDisplay(C);
    	
    	cout << endl << "对B,C串进行模式匹配:"<<endl;
    	cout << Index_KMP(B, C, 1, next) << endl;
    	cout << "输出C的next函数:" << endl;
    	get_next(C, next);
    	for (int  i = 0; i < 8; i++)
    	{
    		cout << next[i]<<" ";
    	}
    	cout << endl;
    	cout << "输出改进后C的next函数:" << endl;
    	get_nextval(C, next);
    	for (int i = 0; i < 8; i++)
    	{
    		cout << next[i]<<" ";
    	}
    	system("pause");
    }
    

    结果

    在这里插入图片描述

    注:使用堆串实现,与书中结果相差1 (因为堆串的首地址是有值的,定长顺序串首地址 放的是串长)

    展开全文
  • 主要介绍了C语言数据结构模式匹配的相关资料,需要的朋友可以参考下
  • 主要介绍了C语言数据结构模式匹配字符定位问题的相关资料,希望通过本文能帮助到大家,让大家理解这部分内容,需要的朋友可以参考下
  • 数据结构与算法实验指导 V2017 常熟理工学院 数据结构与算法实验指导与报告书 _2017-2018_学年 第_1_ 学期 专 业 物联网工程 实验名称 模式匹配 实验地点 N6-210 指导教师 聂盼红 计算机科学与工程学院 2017 ...
  • KMP模式串匹配 想直接使用此代码的朋友可以移步此链接下载jar包,直接导入项目使用, 此jar包后期还会更新更多功能,敬请期待. import java.util.ArrayList; import java.util.List; public class KMP { /** * 求...

    KMP模式串匹配

    想直接使用此代码的朋友可以移步此链接下载jar包,直接导入项目使用,

    此jar包后期还会更新更多功能,敬请期待.

    import java.util.ArrayList;
    import java.util.List;
    
    public class KMP {
    
        /**
         * 求KMP算法的临时数组next[]
         * @param pattern 模式串
         * @return next
         */
        public static int[] computeTemporaryArray(char pattern[]){
            int[] next = new int[pattern.length];
            int j = 0;
            for (int i = 1; i < next.length;) {
                if (pattern[i] == pattern[j]){
                    next[i] = j+1;
                    i++;
                    j++;
                }else {
                    if(j != 0){
                        j = next[j-1];
                    }else {
                        next[i] = 0;
                        i++;
                    }
                }
            }
            return next;
        }
    
        /**
         *
         * KMP算法本体
         * @param text 主串
         * @param pattern 模式串
         * @return boolean
         */
        public static boolean KMP(char[] text , char[] pattern){
            int[] next = computeTemporaryArray(pattern);
            int i=0,j=0;
            while(i < text.length && j<pattern.length){
                if (text[i] == pattern[j]){
                    i++;
                    j++;
                }else{
                    if (j==0){
                        i++;
                    }else {
                        j= next[j-1];
                    }
                }
            }
            if (j == pattern.length){
                return true;
            }
            return false;
        }
    
    
        /**
         * KMP算法本体 返回匹配到的数量
         * @param text 主串
         * @param pattern 模式串
         * @return int 匹配到的字符串的数量
         */
        public static int KMPReturnCount(char[] text , char[] pattern){
            int[] next = computeTemporaryArray(pattern);
            int i=0;
            int j=0;
            int count=0;
            while(i < text.length && j<pattern.length){
                if (text[i] == pattern[j]){
                    i++;
                    j++;
                }else{
                    if (j==0){
                        i++;
                    }else {
                        j= next[j-1];
                    }
                }
                if (j >= pattern.length){
                    j = 0;
                    i++;
                    count++;
                }
            }
           return count;
        }
    
    
        /**
         * KMP算法本体 返回匹配到的所有下标
         * @param text 主串
         * @param pattern 模式串
         * @return List 匹配到的字符串的数量
         */
        public static List KMPReturnIndex(char[] text , char[] pattern){
            int[] next = computeTemporaryArray(pattern);
            int i=0;
            int j=0;
            int index = -1;
            List<Integer> indexList = new ArrayList<Integer>();
            while(i < text.length && j<pattern.length){
                if (text[i] == pattern[j]){
                    if (index == -1){
                        index = i;
                    }
                    i++;
                    j++;
                }else{
                    if (j==0){
                        i++;
                        index = -1;
                    }else {
                        j= next[j-1];
                        index = i - next[j-1];
                    }
                }
                if (j >= pattern.length){
                    j = 0;
                    i++;
                    indexList.add(index);
                    index = -1;
                }
            }
            return indexList;
        }
    
    }
    
    
    展开全文
  • 在这个章节讲了结构、构造的方法、各种对的操作以及从匹配的算法。 结构也是千奇百态,有直接按顺序存储的结构,有链条式的存储结构以及基于顺序存储结构和链条结构的合体的名字索引表。 的...

    这里说了些什么?

    在这个章节讲了串的结构、构造串的方法、各种对串的操作以及从串的匹配的算法。

    1. 串的结构也是千奇百态,有直接按顺序存储的结构,有链条式的存储结构以及基于顺序存储结构和链条结构的合体的名字索引表。
    2. 串的操作有点像C++里面有个库叫sctring的操作,函数名字都一样的,然后就是告诉我们是怎么实现的。
    3. 模式匹配算法是传统的BF算法(一个一个比失败了就挪动一个位置继续比)和KMP算法(牛皮的跳跃式匹配)。关于这个算法我做了一个ppt但是好像不好直接上传,我就上传到了百度云制作了一个链接,链接如下:https://pan.baidu.com/s/1-Sd8K0PLZGfWOthXfSImWA
    4. Friends, never never never give up!

    转载于:https://www.cnblogs.com/dreamworldclark/p/9936582.html

    展开全文
  • 该文档描述了数据结构的相关知识,朴素的模式匹配,KMP模式匹配,相关的概念,基本知识和代码的实现
  • 子串在主串中的定位操作称为串的模式匹配,记为index(s,t,pos),即在主串s中,从第pos个字符开始查找与子串t第一次相等的位置。若查找成功,则返回子串t的第一个字符在主...其中主串称为目标串,子串称为模式串 ...

    模式匹配

    子串在主串中的定位操作称为串的模式匹配,记为index(s,t,pos),即在主串s中,从第pos个字符开始查找与子串t第一次相等的位置。若查找成功,则返回子串t的第一个字符在主串中的位序,否则返回0。其中主串称为目标串,子串称为模式串

    Brute-Force算法

    基本思想

    从目标串的第pos个字符开始与模式串的第一个字符比较,若相等则继续逐个比较后续字符,否则从主串的第pos+1个字符重新和模式串进行比较。以此类推,若存在和模式串相等的子串,则匹配成功返回模式串t的第一个字符在目标串s中的位置;否则,匹配失败返回0。
    Brute-Force算法如下

    int index(string *s,string *t,int pos){
    int i,j;
    if(pos < 1 || pos > s->length || pos > s->length - t->length + 1){
    return 0;
    }//参数非法
    i = pos - 1;
    i = 0;
    while(i < s->length && j < t->length){
    	if(s->ch[i] == t->ch[j]){
    		i++;
    		j++;//继续匹配下一个字符
    	}else{
    		i = i - j + 1;
    		j = 0;//主串、子串指针回溯,重新开始下一次匹配
    }
    }
    if(j >= t->length){
    	return i - t->length + 1;//返回主串中已匹配子串的第i个字符的位序
    }else{
    	return 0;//匹配不成功
    }
    }
    

    该算法较简单且易于理解,但效率不高,因为目标串指针(i)的回溯消耗了大量时间。

    KMP算法

    讨论一般情况,设目标串s=“s0 s1 … sn-1”,模式串"t0 t1 … tm-1",当si != tj 时存在
    "t0 t1 … tk-1" = “tj-k tj-k+1 … tj-1”(0<k<j)
    则下一次比较可以直接从tk与si开始继续下一趟的匹配。若模式串中不存在子串
    "t0 t1 … tk-1" = “tj-k tj-k+1 … tj-1”(0<k<j),则下一次比较从t0开始与si继续下一趟匹配。由此可见,k的取值可以由模式串的构成直接得出,与目标串s没有关系。
    此时令next[j]=k,则next[j]表明当模式串中第j个字符与目标串中si“失配”时,在模式串中需重新和目标串字符si进行比较的字符位置。

    next[j]的实现(修正后)
    void getnext(string *t,int next[]){//由模式串t求出next值
    int j,k;
    j = 0;
    k = -1;
    next[0] = -1;
    while(j < t->length){
    	if(k == -1 || t->ch[j] == t->ch[k]){
    		if(t->ch[j] != t->ch[k){
    			next[j] = k;
    		}else{
    			next[j] = next[k];
    	}else{
    k = next[k];
    }
    }
    
    KMP算法实现
    int KMPindex(string *s,string *t,int pos){
    int next[INIZSIZE],i,j;
    getnext(t,next);
    i = pos - 1;
    j = 0;
    while(i < s->length && j < t->length){
    	if(j == -1 || s->ch[i] == t->ch[j]){
    	i++;
    	j++;
    	}else{
    	j = next[j];
    	}
    }
    if(j >= t->length){
    	return i - t->length + 1;
    }else{
    return 0;
    }
    }
    
    展开全文
  • 模式匹配模式匹配的定义:实现代码: 模式匹配的定义: 实现代码: int Index(SString S,SString T,int pos){ int i = pos,j = 1; while(i <= S.length && j <= T.length){ if(S.ch[i] =...
  • 数据结构——模式匹配算法

    千次阅读 2017-05-10 18:11:09
     串的查找操作也称作串的模式匹配操作,模式匹配操作的具体含义是:在主串(也称作目标串)中,从位置start开始查找是否存在子串(也称作模式串),如在主串中查找到一个与模式串相同的子串,则称查找成功;...
  • 参考资料:《数据结构(C语言版)严蔚敏著》 版权说明:未经作者允许,禁止转载。...模式匹配:在串S中定位某个子串T的操作称为模式匹配,其中串S称为目标串,串T称为模式串匹配成功:在模式...
  • 数据结构 模式匹配

    千次阅读 2020-05-05 16:58:00
    全部每周作业和视频思考题答案和解析 见浙江大学 数据结构 思考题+每周练习答案 题目一:若给定文本长度为 n,模式长度为 m,则库函数 strstr 的最坏时间复杂度是: A. O(nm) B. O(n) C. O(m) D....
  • 字符串:是由零个或多个字符组成的有限序列字串:串中任意个 连续的 字符组成的子序列子串在主串中的位置表示:以子串的第一个字符在主串的位置来表示模式匹配:也就是求子串在主串中的位置模式串:子串二、算法的...
  • 大话数据结构模式匹配KMP 坚持用blog记录学习之路,加油 2019.4.29 音乐陈百强《偏偏喜欢你》 typedef char String[MAXSIZE+1]; /* 0号单元存放的长度 */ // init Status StrAssign(String T,char *...
  • 数据结构__模式匹配_KMP/BF
  • KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特–莫里斯–普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
  • 数据结构- 模式匹配算法 BF和 KMP算法
  • 数据结构之字符串模式匹配

    千次阅读 2018-05-18 22:44:09
    首先我们引入目标串,模式串的概念,而字符串模式匹配就是查找模式串在目标串中的位置。2.brute-Force算法 brute-Force算法,我的理解是这样的。首先设目标串target="t0t1t2t3t4",pattern="p0p1p2&...
  • /* 模式匹配 */ /* KMP匹配算法 */ /* next[j]是指t[j]字符前有多少个字符与t开头的字符相同 比如t="a b a b c" 考虑t[4]='c' 存在 t0t1=t2t3='ab' --->可知next[4]=2 */ void GetNext(SqString t,...
  • 模式匹配数据结构中字符的一种基本运算,给定一个子串,要求在某个字符中找出与该子串相同的所有子串,这就是模式匹配。假设P是给定的子串,T是待查找的字符,要求从T中找出与P相同的所有子串,这个问题成为...
  • 课程名称:数据结构 实验项目名称:基本操作的实现 实验目的: 1.掌握模式匹配操作。 实验要求: 1、 分别使用BF和KMP算法完成模式匹配。 实验过程: 1、 设计完成next值的计算函数; 2、 ...
  • 键盘输入目标串(主串)s、模式串(子串)t,编写程序,实现顺序串的BF模式匹配算法。要求:匹配成功,输出位序,匹配不成功,显示相应提示信息。 例如:s=“aaaabcdcccc”,t=“abcd”。 因为程序很简单,所以就...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,879
精华内容 751
关键字:

数据结构模式串匹配

数据结构 订阅