如何用KMP算法实现字符串匹配搜索（c++实现）

1、问题描述：有两个字符串：txt[] = "AABAACAADAABAABA" pat[] = "AABA"找到pat在txt当中的匹配位置。输出匹配后第一个字符的位置。匹配位置为0，9, 12

3、KMP算法的基本思想：即使当我们的模板检测不匹配时，我们也能够知道模板下一次匹配时主串的一些信息。例子如下：当“AAAA”匹配时,我们知道了主串的一些信息，下一步的匹配只需要检测模板的第四个元素是不是匹配。

5、那么如何如何计算lps[]数组呢,我们采用如下算法：首先lps[0]永远等于0;初始化len =0，i=0， len表示对应字符pat[i]对应的合适前缀长度。增加i，即i=i+1;如果pat[i]等pat[len]的话，len=len+1; lps[i]=len；如果pat[i]不等于pat[len]，len=lps[len-1]，直到pat[i]等于pat[len]，将len赋值给lps[i]。注意len减小到0之后不再减小