文档章节

KMP模式匹配算法

迷途的羔羊
 迷途的羔羊
发布于 2014/05/07 16:27
字数 418
阅读 6
收藏 1

#include <iostream>

#include<time.h>


using namespace std;


void TraditionalStringMatchAlgorithm(char *mainstring,char *targetstring);

/*

有一点可以确认,假如在j点失配,那么从某点开始,到j点失配时,中间的字符长度必然小于targetstring。

只可能出现中间某点包含部分从头开始的段 

*/ 


void KMP_StringMatchAlgorithm(char *mainstring,char *targetstring);

void CalculateStringNEXT(char *targetstring,int *NEXT);


int main(int argc, char *argv[])

{

char mainstring[]="1234567890";

char targetstring[]="4";

int *NEXT,j;

//TraditionalStringMatchAlgorithm(mainstring,targetstring);

//NEXT=CalculateStringNEXT(targetstring);

//for(int i=0;i<strlen(targetstring);i++) cout<<NEXT[i]<<endl;

//KMP_StringMatchAlgorithm(mainstring,targetstring);

//AgainTraditional(mainstring,targetstring);

Again_KMP_StringMatchAlgorithm(mainstring,targetstring);

return 0;

}

void KMP_StringMatchAlgorithm(char *mainstring,char *targetstring)

/*

两个条件: 

1、主串的i值绝对不变 

2、从已匹配的过程中可以得到什么信息 

*/

{

int i=0,j=0,*NEXT;

int mains=strlen(mainstring);

int target=strlen(targetstring);

NEXT=new int[strlen(targetstring)];

CalculateStringNEXT(targetstring,NEXT);

while((i<=mains)&&(j<target))

{

if(j==-1||mainstring[i]==targetstring[j])

{

i++;j++;

}

else

{

j=NEXT[j];

}

}

if(targetstring[j]=='\0'){ 

cout<<i-strlen(targetstring)<<endl;

cout<<"EXIST"<<endl;}

else {cout<<"NOT EXIST"<<endl;}

}

void CalculateStringNEXT(char *targetstring,int *NEXT)//将一个串看做主串与模式串,并利用迭代的方法求出每个位置的NEXT

{

    int i=0,temp,j=-1;

    

    NEXT[0]=-1;

    

    while(targetstring[i]!='\0')

    {

    if(j==-1||targetstring[i]==targetstring[j])//将上一个位置的值与其NEXT值相比较 

    {

    i++;j++;

    if(targetstring[i]!=targetstring[j]) {NEXT[i]=j;}

    else NEXT[i]=NEXT[j];//假如aaab中的第三个出现模式不匹配时,可以跳过与第二个的比较,直接向前移动一个位置 

   }

   else

   {

    j=NEXT[j];

    }

    }

}

void TraditionalStringMatchAlgorithm(char *mainstring,char *targetstring)

{

    int i=0,j=0;

for(i=0;mainstring[i]!='\0';i++)

{

if(mainstring[i]==targetstring[j])

{

j++;

if(targetstring[j]=='\0')

{

cout<<i-strlen(targetstring)+1<<endl;

cout<<"EXIST !!!"<<endl;

break;

}

}

else

{

i=i-j;

j=0;

}

}

cout<<"NOT EXIST"<<endl;


© 著作权归作者所有

上一篇: 广义表的建立
下一篇: 广义表的建立
迷途的羔羊
粉丝 0
博文 2
码字总数 774
作品 0
昆明
程序员
私信 提问
数据结构与算法JavaScript (五) 串(经典KMP算法)

KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右...

文艺小青年
2017/06/01
0
0
KMP 字符串匹配经典算法深度解析

摘要:KMP算法是字符串匹配的经典算法,由于其O(m+n)的时间复杂度,至今仍被广泛应用。大道至简,KMP算法非常简洁,然而,其内部却蕴含着玄妙的理论,以至许多人知其然而不知其所以然。本文旨...

红薯
2011/08/10
2.5K
0
String indexOf 之BF、KMP算法

一. BF算法 BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二...

陶邦仁
2012/11/26
1K
0
kmp模式匹配算法

KMP字符串模式匹配算法: 是由Knuth,Morris,Pratt共同提出的模式匹配算法,其对于任何模式和目标序列,都可以在线性时间内完成匹配查找,而不会发生退化。KMP算法的核心跳转表next进行了多...

一个小妞
2016/12/20
38
2
字串查找算法总结及MS的strstr源码

http://www.cnblogs.com/ziwuge/archive/2011/12/09/2281455.html 首先来说说字串的查找,即就是在一个指定的字串A中查找一个指定字串B出现的位置或者统计其他B在A中出现的次数等等相关查找。...

shzwork
06/01
6
0

没有更多内容

加载失败,请刷新页面

加载更多

maven 环境隔离

解决问题 即 在 resource 文件夹下面 ,新增对应的资源配置文件夹,对应 开发,测试,生产的不同的配置内容 <resources> <resource> <directory>src/main/resources.${deplo......

之渊
今天
8
0
Linux创建yum仓库

第一步、搞定自己的光盘 #创建文件夹 mkdir -p /media/cdrom #挂载光盘 mount /dev/cdrom /media/cdrom #编辑配置文件使其永久生效 vim /etc/fstab 第二步,编辑yun源 vim /ect yum.repos.d...

究极小怪兽zzz
今天
6
0
jar 更新部分文件

C:\Program Files (x86)\Java\jdk1.8.0_102\bin>jar -hIllegal option: hUsage: jar {ctxui}[vfmn0PMe] [jar-file] [manifest-file] [entry-point] [-C dir] files ...Options: -c c......

圣洁之子
今天
9
0
OSChina 周六乱弹 —— 感谢女装红薯开办了这个网站

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @胖达panda:分享歌词: 我有一只小毛驴我从来也不骑,有一天我心血来潮骑着去赶集,我手里拿着小皮鞭我心里正得意,不知怎么哗啦啦,我摔了一...

小小编辑
今天
2.6K
13
DDD(四)

1,引言 软件开发者大多趋向于将关注点放在数据上,而不是领域上。这对于刚入门的DDD的新手而言也是如此。以我目前的思考方式,数据库依然占据主要的地位。开发一个功能,首先我就会考虑我会...

MrYuZixian
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部