这篇参考：数据结构（c语言版）李云清等，算法导论介绍：在文本编辑中，我们经常要找到某个特定的字符或图案。这样一来，就出现了字符串匹配问题。本文从一个简单的字符串匹配算法入手，通过Rabin-Karp算法进阶到KMP算法，从头到尾教你吃透KMP算法。看看《算法导论》这本书对这个字符串问题的定义：假设文本是一个长度为n的数组T[1...n]，模式是一个数组P[1....m]。进一步假设P和T的元素都是属于有限字母表Σ的字符。根据上图，我们来解释一下字符串匹配问题。目标是在文本T=abcabaabcaabac中找到模式P=abaa的所有出现。这种模式在文本中只出现一次，在位移s=3处。位移s=3为有效位移。1.简单字符串匹配算法简单字符串匹配算法使用循环查找所有有效位移。循环为n-m+1=T[s+1....s+m]的每个可能的s值检查条件P[1....m]。NAIVE-STRING-MATCHER(T,P)1n←length[T]2m←length[P]3fors←0ton-m4doifP[1‥m]=T[s+1‥s+m]//对于n-m+1个可能位移s的每一个值，对应字符的比较循环都要执行m次。5然后打印“Patternoccurswithshift”的简单字符串匹配算法，上图是针对文本T=acaabc和模式P=aab。在上面的第四行代码中，对于n-m+1个可能位移s的每一个值，都要执行m次比较对应字符的循环。所以，在最坏的情况下，这个简单模式匹配算法的运行时间是O((n-m+1)m)。------------------------------我举一个具体的例子，给出一个具体的操作过程：对于目的字符串target为banananobano，匹配的字符串模式为nano，下面是匹配过程，原理很简单，与目标字符串的第一个字符进行比较，相同则比较下一个，如果不同就把图案向右移动，然后比较图案的每个字符。该算法的运行过程如下图所示。//索引代表每n次匹配的情况。#include#includeusingnamespacestd;intmatch(conststring&target,conststring&pattern){inttarget_length=target.size();intpattern_length=pattern.size();inttarget_index=0;intpattern_index=0;while(target_index#includeusingnamespacestd;voidcompute_overlay(conststring&pattern){constintpattern_length=pattern.size();int*overlay_function=newint[pattern_length];intindex;overlay_function[0]=-1;for(inti=1;i=0&&pattern[i]!=pattern[index+1]){index=overlay_function[index];}if(pattern[i]==pattern[index+1]){overlay_function[i]=index+1;}else{overlay_function[i]=-1;}}for(i=0;i#include#includeusingnamespacestd;intkmp_find(conststring&target,conststring&pattern){constinttarget_length=target.size();constintpattern_length=pattern.size();int*overlay_value=newint[pattern_length];overlay_value[0]=-1;intindex=0;for(inti=1;i=0&&pattern[index+1]!=pattern[i]){index=overlay_value[index];}if(pattern[index+1]==pattern[i]){overlay_value[i]=index+1;}else{overlay_value[i]=-1;}}//matchalgorithmstartintpattern_index=0;inttarget_index=0;while(pattern_index
