1.实现朴素匹配算法，Rabin Karp算法和Knuth Morria Pratt 算法三种基本字符串基本匹配算法，以及优化算法，即BM算法，BMH算法，Sunday算法。
2.编写函数引入一段较长的英文文本文件，进行匹配测试，由实验得出的数据从时间复杂度分析三种基本字符串匹配算法。
3.针对三种基本字符串匹配算法在一个长文本中匹配一个模式串所耗费的时间，进行结论分析，编写报告。
1.对于给定的字符串，找出与需匹配字符串相对应的段落位置并输出。
2.对查找的过程进行时间层面的分析，包括运行完成所需的时间以及不同算法间的对比。
3.可搜索匹配的对象仅包括：字母，符号及数字。
4.计算机终端输出的结果是:需匹配字符串在所给字符串中的位置，运行算法匹配完成到输出所需的时间。
实验要求实现六个匹配算法，分析三种算法的时间复杂性，通过应用三种算法在一个较长英文文本中查找一个子串的实验数据来对比三种算法的运行时间。涉及的三个算法如下：
1.对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。
2.对主串做大循环，每个字符开头做T的长度的小循环直到匹配成功。
3.返回i的值即为该字符在主子符串的位置。
计算匹配与需匹配字符串的哈希值
1.进行哈希值的比较，相等再进行字符的比较
2.都匹配成功则输出位置，失败返回“未找到”
1.基于回溯法实现
（1） 根据模式串创建next数组
（2）根据next数组在文本串中匹配模式串
2.基于确定有限状态自动机实现
（2）根据模式串创建dp数组（状态转移表）
（3）根据dp数组在文本串中匹配模式串
1.根据模式串构建坏字符表。
2. 根据模式串构建好后缀表。
3. 在文本串中匹配模式串，遇到失配的情况，选择坏字符表和好后缀中相应的值中最大的那一个进行后移。
1.根据模式串构建坏字符表。
2. 根据模式串构建好后缀表。
3. 在文本串中匹配模式串，遇到失配的情况，选择坏字符表和好后缀中相应的值中最大的那一个进行后移。同时忽略好后缀产生的影响，只考虑好字符。
1.将子字符串和主字符串对齐
2.若在第一个位置匹配正确，则顺次匹配下一个位置上的字符直至子字符串完全匹配成功
3.若匹配失败，主子符串则跳至参加匹配的子字符串的最末尾的下一个字符，直接跳过一大片，直至匹配成功
（1）考虑到使用string类型会造成主字符串在匹配过程中出现无法正确读取输入信息，故改为char类型，方便读取运算。为了与主子符串对应，故将子字符串也改为char类型。
（2）在原来设计中，由于考虑子字符串匹配主字符串出现重复的问题，后修改设计，使得子字符串在主子符串出现的首个位置为最终需要匹配的位置。
（1）考虑到哈希值有多种计算方式，可能导致实验数据的结果产生偏差，所以对算法进行了代码层面的比较，最后选择了除余法，其计算公式：d%q*p+P[i]-'a'（d为一个素数）
（2）在运行测试的过程中有极小的可能，会在计算哈希值时产生哈希冲突，为了代码的完整全面，加入了防止冲突的函数
（1）KMP算法实现有两种方式，一个基于回溯，一个基于确定有限状态自动机，利用回溯实现的代码可以匹配数字，字母，空格等其他字符，而利用确定有限状态自动机实现代码只能匹配在ASCII表中的256个字符，无法匹配中文。
（2）当匹配成功时，会显示模式串在文本串匹配的首位置。匹配失败，则会提示匹配失败。
设（n为主串长度，m为模式串长度）
时间复杂度的情况分析如下:
a) 最好情况
O(1) 一开始就匹配成功。
b) 最坏情况
O((n-m+1)*m) 每次不成功的匹配都发生在模式串的最后一个字符。
c) 平均情况
O(n+m) 根据等概率原则，平均是(n+m)/2次查找。
该算法的主要改进就是先对两个需匹配字符串进行哈希值的运算，再进行比较，这就运用到了哈希算法。哈希算法可以有很多种不同的形式，它可能包含ASCII码字符以便对数字进行转化，但也可能是别的形式。我们唯一需要的就是将一个字符串（模式串）转化成为能够快速进行比较的哈希值。以"hello world"为例，假设它的哈希值hash('hello world')=12345。那么如果hash('he')=1，那么我们就可以说模式串"he"包含在文本"hello world"中。由此，我们可以每次从文本中取出长度为m（m为模式串的长度）的子串，然后将该子串进行哈希，并将其哈希值与模式串的哈希值进行比较。
假设在M字符串中找N字符串的起始位置，长度分别为m和n，使用KMP算法，一般认为时间复杂度是O（m+n），也就是计算next数组的时间复杂度是O(n)，而匹配的时候是O（m）。
BM算法被认为是亚线性串匹配算法，它在最坏情况下找到模式所有出现的时间复杂度为O(mn)，在最好情况下执行匹配找到模式所有出现的时间复杂度为O(n/m)。
（1）status InitData(char **S,char **T)频度为i+1
（2）findindex(char *T,char temp)频度为i+1
（3）Sunday(char *S, char *T)
设（m为主串长度，n为子串长度）时间复杂度的情况分析如下:
① 平均性能的时间复杂度为O(n)；
② 最差情况的时间复杂度为O(n * m)
设匹配字符串长度为M，被匹配字符串长度为N，将两个字符串先对齐后从后往前匹配。当失配时，搜索对齐位置末尾的字符在匹配字符串中从后往前最先出现的位置(预处理后时间复杂度为O(1) )k，移动m-k-1位，如果不存在则会初始化为-1。该算法的理想复杂度为N/M，期望复杂度为N，最坏复杂度为N*M。
实验要求实现朴素匹配算法，Rabin-Karp算法 和KMP算法的代码实现和通过应用三种算法在一个较长英文文本中查找一个子串的实验数据来对比三种算法的运行时间。对于这三种算法，我们主要查阅了严蔚敏老师的的《数据结构》，《算法四》，《算法导论》以及一些博客贴。
我们从一部小说节选了10165个字符的文本串，进行对比运行时间。为了精准对比运行时间，我们分别在文本中的第1000,2000,5000,7000和10000附近的位置选取模式串，进行匹配。
通过运行时间对比显示，RK算法始终花费最多的时间，因为无论要搜索何处的模式串，都需要对整个文本串进行预处理，测试的文本串具有10165个字符，导致运行时间加大。截取文本串7000位的模式串的长度是其他模式串的两倍，因此导致时间加大。
朴素匹配算法和KMP算法有着密切的关系，因此单独将这两个算法进行对比，可以发现匹配5000位之前的模式串，从运行时间的角度上来说，KMP是优于朴素匹配算法的，但是对于5000之后的模式串来说，朴素匹配算法优于KMP算法。从匹配7000位字符的模式串的运行时间来看，模式串的长度影响了运行时间。此文本串很少有重复的单词，因此会频繁地遇到失配的情况，KMP算法是不退回的算法，最坏情况下近乎于遍历文本串。
由上所述，KMP算法和RK算法虽然对朴素匹配算法进行了相对显著的优化，但是应用于实际问题中，效率依旧不理想。我们查阅了相关的资料，发现文本编辑器，编译器中的查找功能往往是基于BM算法而实现的，BM算法于1970年由德克萨斯大学的两名教授发明的，至今有很多优化算法，比如本实验拓展部分的Sunday，BMH算法。
本报告涉及的六种字符串匹配算法属于单模式匹配，即在文本中寻找一个子串，如果需要同时在文本中查找多个子串，需要用到字典树，AC自动机等算法。