概念：
由零个或者多个字符组成的有限序列叫做串
任意多个连续的字符组成的子序列称为该串的子串
饱含着子串的串称为主串
数据结构定义
#include
#include
#include
typedef struct {
char ch[10];
int length;
} SString;
void main()
{
SString s;
s.length = 5;
char a[5] = {'H','e','l','l','o'};
memcpy(s.ch , a,strlen(a));
for(int i = 0; i<s.length; i++){
printf("%c\n",s.ch[i]);
}
}
关于串的使用很简单，重点只在于子串的匹配算法。
（1）简单模式匹配
思想非常简单，拿着子串从主串第一个字符开始，一个个下标位置进行比较，有一个没对上，则进行下一位置的继续比较。
更通俗的说，就是逐个字眼比较即可
1:以子串为外层循环，主串为内层循环，拿一个子串的元素开始扫主串的元素，遇到匹配的，则子串下标指针和主串下标指针同时移动1，即比较下一个；若不匹配，主串的下标指针移动1, 子串移动回串头位置，准备重新匹配；
#include
#include
#include
typedef struct {
char ch[10];
int length;
} SString;
void main()
{
SString s;
s.length = 5;
char a[5] = {'H','e','l','l','o'};
memcpy(s.ch , a, strlen(a));
char b[2] = {'l','o'};
for(int i = 0; i<s.length; i++){
int j = i;
int k = 0;
while(s.ch[j] == b[k]){
printf("匹配成功: %c\n",s.ch[j]);
k++;
j++;
if(k>1){
printf("全部匹配成功\n");
return;
}
}
printf("字符串%c匹配失败\n",s.ch[j]);
}
}
其中两层循环嵌套，一层是循环主串的，一层循环子串的，所以最坏的时间复杂度是O(M N)，即假设每次都匹配到最后一个元素失配，即差不多每执行一次外层，内层都跑N次，那么M次外层，就是M N次总执行。
通过上面例子可以看出，假如子串很长，例如有6000位，主串上百万位，当每次都是从i开始匹配成功第一个，然后子串跟主串指针同时后移，且匹配到5998位失配，子串的指针仍然会移动回到0位继续跟主串i+1位置比较，这无疑是非常低效率的
（2）KMP算法
根据上面例子，造成低效率的根本原因就是指针的回溯，那么我们设想，假如子串和主串既然比较了前0～N个元素都是相同的，那么当子串中有一部分是相等的，例如：子串为aabaac, 其中aa就是一个相等的前后缀，假如主串是比较到后面的aac才发现不等，那么就证明主串的前面的aa这一部分其实跟子串是匹配的，那么我们其实可以让主串的指针不要动，我们把子串的指针回溯到前缀的aa的位置，再进行比较，看aab是否相等，同时，aa这个相等部分我们也可以不比较了，从第三个位置的元素开始比较（这一部分很难懂没关系，看完下面的例子一定可以理解）
可是问题就在于，我怎么知道子串指针回溯到哪里？子串上一个对应的最大前缀在下标哪个位置？这就需要Next数组来帮忙了
Next数组其实就是形容当第X位置发生失配情况时，子串的指针应该回溯到哪个位置
怎么求next数组？
例一：假设子串S=’aaab’ ；求next数组
首先如果第一位就发生失配，那根本没得回溯，所以第一位固定是 0
如果第二位发生失配，那么证明第一位是匹配的，所以第二位固定是回溯到 1
假如第三位发生失配，证明主串前两位aa是跟子串匹配的，但是第三位不匹配，那么就要看前缀了：
设第三位为？
同时把子串往后挪一位，找到最大匹配前缀，得到：
用第二个a和？相比较，看？会不会等于a，这也就是说。子串的下标应该回溯到第2个元素。
所以数组第三个位置失配，就要回溯到2
假如是第四个位置发生失配，那么就是：
用子串第三个位置的a跟？比较，看？是不是a
也就是子串指针回溯到第3个位置
如果第四个位置也没发生失配，那就是配对成功～
所以next数组值为：0123
; 总结：求next数组值步骤如下
1: 前两位固定0 1
2：从第三个位置开始，把子串往后挪动，找到左边线部分上下最大的匹配前缀，也就是左边线上下两字符串必须完全匹配；右边线的子串位置就是next数组下一次要比较的值的位置，也就是回溯位置。
3: 若子串完全挪过中间线，也没找到两字符串匹配的位置，next数组值设为1；也就是它们已知的部分一个都匹配不上，只能从头第一个开始匹配。
例2: 求 ababaaababaa 的next数组：
还有一种说法是next数组前两位固定为 -1 0
其实就是把上面求出来的next数组集体-1即可
; 经过上面的计算例子，我们可以隐约有种感觉，next数组对应位置的值next[i] 其实就是子串在第i个位置发生失配时，子串的指针回溯到next[i] 的位置，主串指针不变，然后子串的第next[i] 个元素与主串失配的那个元素再次比较看是否相等。
具体怎么跟主串再次比较呢？还是例子比较好理解：
例3 设有字符串S = ‘aabaabaabaac’, P = ‘aabaac’
(1) 求P的next数组
; （2）若S是主串，P是模式串，描述KMP算法的匹配过程
主串S = ‘aabaabaabaac’
模式串P = ‘aabaac’
（1）首先比较逻辑还是一样，假如S[j] = = P[i] ；i j++ 进行下一个比较
（2）比较到aabaa都匹配符合，到了第六位，发生失配，这个时候即是i=6，找到i=6的next值，发现是3，则子串回溯到i=3的位置, 注意此时主串指针j=6不需要回溯 ，即用P[3] = b和主串第六位进行比较，发现b == S[6],
（3）继续往下匹配，i j ++ ；直到 P[6]=c , S [9] = a ,又发生失配，这个时候 i又是 6，找到i=6的next值，发现是3，则子串回溯到i=3的位置
（4）P[3] = = S[9] = = b, 则 i j ++ 继续往下
（5）这次匹配到P[6] = = S[12] = = c 都没有发生失配，此时子串结束，标志着匹配成功！
这就是匹配的整套流程
知道理解并且能够模拟KMP匹配过程后，可以看一些王道书摘抄出来的历年真题加深印象，其实明白了过程，做题就很简单了
第八题和第九题的Next数组计算出来都是：0 1 1 2 2 3
第八题，第一次失配，是s[5] != t[5] 即 a != c 按照KMP的特色，主串S指针 i 不回溯，子串指针根据next数组回溯到第三个 3 位置 ，但是又由于它这里下标从0开始，所以应该是 t[ 2 ]
所以 i = 5; j = 2
第九题，计算比较次数，首先开始比较是：a= =a b= =b a= =a a= =a b= =b 都匹配，第六次比较 a!=c ，此时子串回溯到3，也就是 a
子串的前缀ab已经不需要再比较了
然后继续比较：a= =a a= =a b= =b c= =c 完成匹配
所以一共进行了：6+4 = 10次 比较
; （3）KMP的优化
KMP的优化，其实是对Next数据的优化，优化后叫做NextVal数组，比Next性能要更好一点
若失败后，i 指针回溯所指向的字符，与匹配串中失配时 i 指针指向的字符一样，则让 i 进行”二次回溯”，直接回溯到next对应的序号所指向的next位置
更通俗点讲：假如我子串是匹配到 i = 6 ; P[6] = a 匹配失败的，根据next数组，回到 i = 3 的位置，但是 P[3] = a ; 那么本来我就是匹配a失败的，你又让我回溯拿着 a去做明知道失败的匹配，完全就是浪费时间！那干脆直接给我 i = 3 失配时，你还要往后跳的 i 就得了！
按这个道理，如果 对应i 回溯的值一直是同一个，则会一直回溯！直到值不相同，这个时候拿着去比较才有意义！
还是看例子：
例1: 求 ababaaababaa 的next val数组：
这个数组是我们之前求过的可以直接拿它的计算结果：
填写步骤：
从前往后填：
1发生失配，没得跳，还是0
2发生失配，跳回1，a != b ，值不相等，不用覆盖
3发生失配，跳回1，此时 p[3] == p[1] = = a ; 所以3发生失配时,直接拿1的next值，所以next val = 0
4发生失配，跳回2，此时 p[4] = = p[2] = = b ; 所以4发生失配时,直接拿2的next值，所以next val = 1
5发生失配，跳回3，此时 p[5] = = p[3] = = a ; 所以5发生失配时,直接拿3的next值，所以next val = 0
6发生失配，跳回4，此时 p[6] != p[4] 字符不相同，肯定需要比较一下，不能跳; 所以6发生失配时next val 的值跟 next 的值一样 , next val = 4
。。。。。。按照这个逻辑，一步步推算下去，很简单，但是第一轮做肯定有点磕磕碰碰，到最后输出：
; （4）时间复杂度
有上面例子可以看出，KMP最主要的两部操作：
（1）循环生成Next数组/或者NextVAL ， 设子串规模为M，则仅仅需要 O(M)
（2）对照着数组这一”导航地图”，子串和主串进行字符串匹配，其中主串不需要回溯，设主串数据规模为N ,仅仅需要O(N)
一共就是：O（M+N）
以上就是小弟对串匹配算法的一些总结和理解，如果有不对的地方欢迎大佬们指正一起讨论哈～
Original: https://blog.csdn.net/whiteBearClimb/article/details/127817796
Author: 凉拌海蜇丝
Title: 第四章：串（KMP算法和KMP优化）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/659393/
转载文章受原作者版权保护。转载请注明原作者出处！