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}]
评论信息
其他资源
- 人工神经网络 基于CNN卷积神经网络 基于Python 实现图片验证码的识别
- B/S结构 (Java )通讯录
- 进化策略算法
- ATF54143 ADS模型库
- 人脸识别实验报告（含代码及优化）
- 华为企业无线胖AP配置教程
- msp432.rar
- STM32寄存器手册
- windows64位平台的hadoop2.8.4插件包(hadoop.dll,winutils.exe) 下完你回感谢我的！！！！
- 单周期CPU代码实现
- Robo Pro 软件下载
- 射频识别（RFID）技术——无线电感应的应答器和非接触IC 卡的原理与应用2
- arcgis10.5破解文件，包含desktop，portal以及arcgis server
- 7-10-1(遍历Body).7z
- svn下载的python接口函数库
- 非银支付机构20210127.xlsx
- HTML5游戏源码,（QQ）微信80个小游戏源码。
- 2018年统计局数据源 省市区县乡 5级地区行政划分 713479条数据源
- windows画图软件课程设计报告
- 单片机光敏电阻源码
- h265 裸流文件
- 酒店管理系统 c++的代码
- 线性表基本运算的图形模拟演示设计
- RADAN7地质雷达数据处理软件V7.4.16.0404最新版
- db2数据库系统加固规范
- 韦东山JZ2440第三版原理图
免责申明
【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【只为小站】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明