首页 资讯 应用 高压 设计 行业 低压 电路图 关于

单片机

旗下栏目: PLC 嵌入式 单片机 DCS

KMP,NEXT数组,BF算法

单片机 | 发布时间:2018-06-01 | 人气: | #评论# | 本文关键字:算法,KMP算法,NEXT数组,BF算法
摘要:看了好多关于KMP算法的书籍和资料,总感觉没有说的很清楚,为什么会产生next数组,为什么给出了那么简短的程序,没有一个过程,而有的帖子虽然next及其字符串匹配说的很清楚,但是推理的

看了好多关于KMP算法的书籍和资料,总感觉没有说的很清楚,为什么会产生next数组,为什么给出了那么简短的程序,没有一个过程,而有的帖子虽然next及其字符串匹配说的很清楚,但是推理的一些过程相当复杂,比较抽象,今天在这里简单的提一下我的理解,尽可能的把这个过程讲的简单,容易理解。从模式匹配之初:我们先是研究的是BF算法,鉴于我们经常行的需要回溯,总是做一些无用功,为了提高算法的时间度和空间度,引入了next数组(至于为什么提高时间,下面会提到),也就是采用next数组,我们不需要再去回溯了,可以直接比较,这也就是KMP算法了,所以说:从BF到KMP,只是简单的嫌弃BF算法,花费的时间空间太长太大了而已,一切都在进步!!!

串的模式匹配或者串匹配:子串的定位操作是找子串在主串中从POS个字符后首次出现的位置,一般将主串S称为目标串,子串T称为模式串

BF算法:

Brute-Force,也称为蛮力(暴力)匹配算法

1,从主串S的第pos个字符开始,和模式串T的第一个字符进行比较,

2,若相等,则逐个比较后续的字符;不然,就回溯到主串的第POS+1个字符开始,继续和模式串T的第一个字符进行比较,反复执行步骤2,知道模式串T中的每一个字符都和主串相等(返回当前主串S匹配上的第一个字符)或者找完主串S(POS位置后的所有字符(返回0)),

程序1:

  1. #include <stdio.h>                                                                                                    

  2. #include <string.h>  

  3. #include <malloc.h>  

  4. int BFmode(char *s, char *t, int pos)  

  5. {  

  6.         int flag1,flag;  

  7.         int i,j;  

  8.         int slength, tlength;  

  9.         slength = strlen(s);  

  10.         tlength = strlen(t);  

  11.   

  12.         for(i = pos; i < slength; i++)  

  13.         {  

  14.                 flag1 = i,flag = 0;  

  15.                 for(j = 0; j < tlength; j++)  

  16.                 {  

  17.                         if(s[i] == t[j] && i < slength)  

  18.                         {  

  19.                                 flag ++;  

  20.                                 i++;      

  21.                         }  

  22.                         else  

  23.                                 break;    

  24.                 }  

  25.                 if(flag == tlength)  

  26.                 {  

  27.                         return flag + 1;  

  28.                 }  

  29.                 i = flag1;  

  30.         }  

  31.   

  32.         return 0;  

  33. }   

  34.  int main()  

  35. {  

  36.         char s[50];   //目标串  

  37.         char t[20];   //模式串同时也是子串  

  38.         int pos;  

  39.         scanf("%s", s);  

  40.         scanf("%s", t);  

  41.         scanf("%d", &pos);  

  42.         pos = BFmode(s,t, pos);  

  43.         printf("POS:%d\n", pos);  

  44.         return 0;  

  45. }             

编写完了之后,总觉得怪怪的,程序不应该这么复杂啊,

程序2:

int BFmode(char *s, char *t, int pos)  

  1. {  

  2.         int flag1,flag;  

  3.         int i,j = 0;  

  4.         int slength, tlength;  

  5.         slength = strlen(s);  

  6.         tlength = strlen(t);  

  7.         for(i = pos; i < slength && j < tlength; i++)  

  8.         {  

  9.                 if(s[i] == t[j])  

  10.                 {  

  11.                         j++;      

  12.                         if(j == tlength)  

  13.                                 return i - j + 2;         

  14.                 }  

  15.                 else  

  16.                 {         

  17.                         i = i - j;  

  18.                         j = 0;    

  19.                 }  

  20.         }  

  21.         return 0;  

  22. }  

我们还可以将程序优化一下:毕竟程序的重点是(时间和空间),算法比较简单,但是在最坏的情况下,算法的时间复杂度为O(n×m),n,m分别为主串和模式串的长度。从第一个程序就可以很容易的看出来了,主要时间都耗费在失配后的比较位置有回溯,主要都给拉回来,因而比较次数过多,为了时间都不浪费在主串的回溯上面,那么我们引入了next数组

什么是next数组呢?

责任编辑:BF算法
首页 | 电气资讯 | 应用技术 | 高压电器 | 电气设计 | 行业应用 | 低压电器 | 电路图 | 关于我们 | 版权声明

Copyright 2017-2018 电气自动化网 版权所有 辽ICP备17010593号-1

电脑版 | 移动版 原创声明:本站大部分内容为原创,转载请注明电气自动化网转载;部分内容来源网络,如侵犯您的权益请发送邮件到[email protected]联系我们删除。

Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。