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}]
评论信息
其他资源
- ClearCanvas开源PACS系统C#
- 最小二乘法汇总及matlab仿真
- 图像识别检测人数
- 传统方法目标识别 代码
- 工程优化方法（西电版）
- 4x4按键资源，包含stm32代码，各种资料，使用心得，是做电子设计竞赛过程中一步步整理出来的，觉得好别忘了好评
- ANSYS Electronics Desktop 2019R1 Q3D Extractor帮助文件
- 嵌入式系统原理及应用.pdf
- 降低OFDM峰均比的matlab仿真
- C# SqlServer 商品销售管理系统
- 置乱变换matlab代码
- 区块链加密货币交易app静态模板.rar
- VisualC#2015资料库程式设计暨进销存系统实作+Source Code
- 工作正在进行中-源码
- MakeFile解释.docx
- 第2部分：门（急）诊病历.xml
- fst：R的数据帧的快速闪电序列化-源码
- .net学校学籍管理系统源码.zip
- 阵列非线性产物辐射方向图分析仿真程序
- 客户管理系统JAVA
- 解决 PL/SQL Developer提示：无法锁定oci dll
- Nbtstat（Delphi版）
- JAVA销售管理系统
- 遗传算法matlab源代码
免责申明
【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【只为小站】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明