c语言数据结构字符串模式匹配算法.zip
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。
一.简单匹配算法
先来看一个简单匹配算法的函数：
int Index_BF ( char S [ ], char T [ ], int pos )
{
/* 若串 S 中从第pos(S 的下标0≤pos S[0] != S[1],S[1] != S[2],所以S[1] != T[0],S[2] != T[0]. 还是从理论上间接比较了。
有人疑问又来了，你分析的是不是特殊轻况啊。
假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=-1，意思是S[2]已经和T[0] 间接比较过了，不相等，接下来去比较S[3]和T[0]吧。
假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=0，意思是S[2]已经和T[2]比较过了，不相等，接下来去比较S[2]和T[0]吧。
假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S[5]和T[5]时，发现不等，就去看next[5]的值，next[5]=2，意思是前面的比较过了，其中，S[5]的前面有两个字符和T的开始两个相等，接下来去比较S[5]和T[2]吧。
总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值next[n]呢？（本文中next值、模式函数值、模式值是一个意思。）
三. 怎么求串的模式值next[n]
定义：
（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1—k个字符与开头的1—k
个字符不等（或者相等但T[k]==T[j]）（1≤k0 但k
#include
int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{
if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//
return -1;//空指针或空串，返回-1。
int len=0;
const char * c=Pattern;
while(*c++!='\0')//移动指针比移动下标快。
{
++len;//字符串长度。
}
int *next=new int[len+1];
get_nextval(Pattern,next);//求Pattern的next函数值
int index=0,i=0,j=0;
while(Text[i]!='\0' && Pattern[j]!='\0' )
{
if(Text[i]== Pattern[j])
{
++i;// 继续比较后继字符
++j;
}
else
{
index += j-next[j];
if(next[j]!=-1)
j=next[j];// 模式串向右移动
else
{
j=0;
++i;
}
}
}//while
delete []next;
if(Pattern[j]=='\0')
return index;// 匹配成功
else
return -1;
}
int main()//abCabCad
{
char* text="bababCabCadcaabcaababcbaaaabaaacababcaabc";
char*pattern="adCadCad";
//getNext(pattern,n);
//get_nextval(pattern,n);
cout<
文件下载
资源详情
[{"title":"（ 26 个子文件 418KB ） c语言数据结构字符串模式匹配算法.zip","children":[{"title":"字符串模式匹配算法","children":[{"title":"优化算法","children":[{"title":"优化算法.opt <span style='color:#111;'> 47.50KB </span>","children":null,"spread":false},{"title":"优化算法.dsw <span style='color:#111;'> 524B </span>","children":null,"spread":false},{"title":"优化算法.c <span style='color:#111;'> 1.67KB </span>","children":null,"spread":false},{"title":"优化算法.ncb <span style='color:#111;'> 41.00KB </span>","children":null,"spread":false},{"title":"优化算法.dsp <span style='color:#111;'> 3.34KB </span>","children":null,"spread":false},{"title":"Debug","children":[{"title":"优化算法.ilk <span style='color:#111;'> 183.41KB </span>","children":null,"spread":false},{"title":"vc60.pdb <span style='color:#111;'> 52.00KB </span>","children":null,"spread":false},{"title":"优化算法.exe <span style='color:#111;'> 180.11KB </span>","children":null,"spread":false},{"title":"优化算法.obj <span style='color:#111;'> 6.98KB </span>","children":null,"spread":false},{"title":"vc60.idb <span style='color:#111;'> 33.00KB </span>","children":null,"spread":false},{"title":"优化算法.pch <span style='color:#111;'> 180.52KB </span>","children":null,"spread":false},{"title":"优化算法.pdb <span style='color:#111;'> 441.00KB </span>","children":null,"spread":false}],"spread":true},{"title":"优化算法.plg <span style='color:#111;'> 681B </span>","children":null,"spread":false}],"spread":true},{"title":"传统算法","children":[{"title":"传统算法.dsw <span style='color:#111;'> 524B </span>","children":null,"spread":false},{"title":"传统算法.c <span style='color:#111;'> 1.13KB </span>","children":null,"spread":false},{"title":"传统算法.plg <span style='color:#111;'> 756B </span>","children":null,"spread":false},{"title":"传统算法.opt <span style='color:#111;'> 47.50KB </span>","children":null,"spread":false},{"title":"Debug","children":[{"title":"vc60.pdb <span style='color:#111;'> 52.00KB </span>","children":null,"spread":false},{"title":"vc60.idb <span style='color:#111;'> 33.00KB </span>","children":null,"spread":false},{"title":"传统算法.exe <span style='color:#111;'> 180.11KB </span>","children":null,"spread":false},{"title":"传统算法.ilk <span style='color:#111;'> 188.87KB </span>","children":null,"spread":false},{"title":"传统算法.obj <span style='color:#111;'> 5.54KB </span>","children":null,"spread":false},{"title":"传统算法.pch <span style='color:#111;'> 180.44KB </span>","children":null,"spread":false},{"title":"传统算法.pdb <span style='color:#111;'> 441.00KB </span>","children":null,"spread":false}],"spread":true},{"title":"传统算法.ncb <span style='color:#111;'> 41.00KB </span>","children":null,"spread":false},{"title":"传统算法.dsp <span style='color:#111;'> 3.34KB </span>","children":null,"spread":false}],"spread":true}],"spread":true}],"spread":true}]
评论信息
其他资源
- Appinventor2 游戏源码--仿像素鸟
- 网上教学辅助系统
- 数学建模之全球环境统计数据（一）
- VC++ MFC MSCOMM VS2010 手把手学会串口收发 例程
- gangqin.zip
- element-ui-api 离线文档
- Android下自动连接指定SSID的WIFI的简单实现的demo
- 水文频率计算软件
- 战德臣计算机思维导论mooc全部习题及答案解析
- SCM信道模型
- G.711播放器和编解码库和转换（包括ulaw和alaw测试文件）
- 海康NetVideoActiveX23
- ISO26262-6 中文版内部资料
- mfc调用webservice的客户端
- 分享一款监控网络设备
- 基于互补序列的OFDM系统载波频率偏移估计
- 课时4：MongoDB数据库管理备份.mp4
- 油井生产数据采集与管理系统软件的设计与开发
- 黑莓热键大师
- 2017 全域旅游发展报告.pdf
- SLE-11-SP4-SAP-DVD-x86_64-GM-DVD1.iso
- WPF,好看的圆形ProgressBar实现
- 基于正反切函数的无位置传感器控制.rar
- javaweb图书馆管理系统
- ps2键盘程序，已成功。
- 基于Qt+SQLite的简单的学生信息管理系统c++
- java读取excel ，xls和xlsx
免责申明
【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【只为小站】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明