KMP 快速匹配算法
最近学习了KMP快速匹配算法，自己动手尝试着编写，最终也完成了该算法，理清思路后发表该博客，希望不懂的小白可以参考（我也是小白）
首先KMP算法是字符串快速匹配算法。简而言之就是快速在一个字符串里查找相应的内容。比如word的查找功能
模拟应用场景： 在asdasdasdddasdasd 快速找到asddd第一次出现时对应下标。
一般的串匹配算法（非KMP算法）：
KMP算法：
设主串（T）为：a b a c a a b a c a b a c a b a a b b
模式串（W）为：a b a c a b
而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。
比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。
在第一次匹配过程中
T : a b c a b c a b c a a a b c
W: a b c a b c a a
在T[7]与W[7]出现了不匹配，而T[0]~T[6]是匹配的，现在T[0]~T[6]就是上文中说的已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠：移动一次出现以下(仅仅一次)
T : a b c a b c a b c a a a b c
W: a b c a b c a a
此时直接从W[4]与T[7]开始一一对应往下匹配，发现立即找到了符合条件的下标
然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。
但是如何找到W[4],让其与T[7]开始匹配首先我们分析下a b c a b c a a这个数据
当a b c a b c a a中红色a与T开始匹配时，失陪（没有匹配成功）但是前面的abc出现了两次也就说明T串中前7个是匹配成功的。
此时我们可以直接让W[0]与T[3]对应，对应后发现
T : a b c a b c a b c a a a b c
W: a b c a b c a a
W中红色b之前的还是匹配的，也就是T[7]不需要回到T[3]开始匹配。这样的话我们只需要找到移动W串相应的步数即可！
| j下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| W[j] | a | b | c | a | b | c | a | a |
| F(j) | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
F（j）为不需要匹配的个数（即从F(j)出开始匹配）如W[6]对应的F[j]为3 即为W中前三个不需要匹配.
以下为计算F[j]代码：
int *getfreq(char *str) {
int *freq = NULL;
int i = 0;
int j = -1;
freq = (int *) calloc(strlen(str) + 1, sizeof(int));
freq[0] = -1;
while(i < strlen(str)) {
if(j == -1 || str[j] == str[i]){
i++;
j++;
freq[i] = j;
}
else{
j = freq[j];
}
}
freq[0] = 0;
return freq;
}
做到这一步已经完成了一大半：下面就是用freq数组进行移动！
整体代码如下
#include <stdio.h>
#include <malloc.h>
#include <string.h>
void getindex(char *str1, char *str2, int *freq) {
int i = 0;
int j = 0;
int flog = 1;
while(str1[i] != 0 && flog == 1){
if(str1[i] == str2[j]){
i++;
j++;
}
else{
j = freq[j];
i++;
}
if(j == strlen(str2)){
flog = 0;
}
}
if(flog != 0){
printf("没有找到");
}
else{
printf("第一次该内容对应的下标为：%d", i - strlen(str2));
}
}
int *getfreq(char *str) {
int *freq = NULL;
int i = 0;
int j = -1;
freq = (int *) calloc(strlen(str) + 1, sizeof(int));
freq[0] = -1;
while(i < strlen(str)) {
if(j == -1 || str[j] == str[i]){
i++;
j++;
freq[i] = j;
}
else{
j = freq[j];
}
}
freq[0] = 0;
/*for(i = 0; i < strlen(str); i++){
printf("%d",freq[i]);
}*/
return freq;
}
int main(){
char s1[100];
char s2[100];
int *freq = NULL;
printf("请输入源字符串:\n");
gets(s1);
printf("请输入要查找的内容:\n");
gets(s2);
freq = getfreq(s2);
getindex(s1, s2, freq);
free(freq);
return 0;
}