数据结构，算法与应用 ---C++语言描述(代码与习题答案）数据结构，算法与应用 ---C++语言描述(代码与习题答案）
2022-12-03 21:18:03
1.62MB
1
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<
2022-12-03 21:12:51
418KB
1
适用于新手的Python基本数据类型查阅文档
2022-12-03 19:25:20
8.42MB
1
课程设计 大二的自己的课程设计 主要是哈夫曼编码和译码的c++的程序 包括根据字符的权重进行编码 并对文件进行编码译码
2022-12-03 17:24:30
572KB
1
本书以数据结构基础和算法设计方法为知识单元，系统地介绍了数据结构与算法的基本知识及应用，简明扼要地阐释了计算机算法的设计与分析方法。本书的主要内容包括线性表、树、图等基础数据结构，同时也包括一些实用性较强的算法及高级数据结构，如并查集、伸展树等。以经典问题算法为例，书中分类介绍了算法设计方法以及查找与排序算法等。编者结合ACM国际大学生程序设计竞赛的需求，对各章节知识的灵活应用进行了详细的分析，用丰富的实例帮助读者由浅入深、快速地掌握算法设计的技巧，提升算法设计能力。
2022-12-03 16:37:39
5.28MB
1
什么是数据结构？简单的说，就是数据在内存里的组织，存储，运算操作的总和。
在计算机出现的初期，算法成了核心，但随着当今数据量的大量出现，研究数据结构就发展起来了一门学科
2022-12-03 14:05:17
22.39MB
1
Java语言实现冒泡排序和快速排序的交互动画，是我的课程设计，内附文档ppt以及源码，可以直接运行。利用javafx中的柱状图进行实现。
2022-12-02 23:40:16
72.54MB
1