C 语言字符串模式匹配
本文将详细介绍 C 语言中的字符串模式匹配算法，包括 Brute Force 算法（BF 算法）和 KMP 算法。这些算法都是解决字符串模式匹配问题的常见方法。
BF 算法（Brute Force 算法）
BF 算法是一种蛮力算法，用于解决字符串模式匹配问题。该算法的思想是从主串的第一个字符和模式串的第一个字符开始比较，如果相等，则继续比较后续字符；否则，从主串的下一个字符开始重新和模式串的字符比较。该算法的实现如下所示：
```c
int Index(char* strS, char* strT, int pos) {
int i = pos;
int j = 0;
int k = 0;
int lens = strlen(strS);
int lent = strlen(strT);
while(i < lens && j < lent) {
if(strS[i+k] == strT[j]) {
++j;
++k;
} else {
i = i+1;
j=0;
k=0;
}
}
if(j >= lent) {
return i;
} else {
return 0;
}
}
```
该算法的时间复杂度为 O(m*n)，其中 m 是主串的长度，n 是模式串的长度。在最好的情况下，时间复杂度为 O(n)，而在最坏的情况下，时间复杂度近似于 O(m*n)。空间复杂度为 O(1)，不需要额外开辟空间存储。
KMP 算法
KMP 算法是一种线性时间复杂度的字符串匹配算法，它是对 BF 算法的改进。该算法的思想是利用已经得到的部分匹配信息来进行后面的匹配过程。其时间复杂度为 O(m+n)，空间复杂度为 O(n)。
在 KMP 算法中，next 数组是关键结构，它用于存储模式串的部分匹配信息。next[j] 表示当 pi 不等于 tr 时，下一次将 p next[i] 与 tr 开始继续后继对应字符的比较。next 数组的定义如下：
```c
next[0] = -1;
for(int i = 1; i < n; ++i) {
j = next[i-1];
while(j != -1 && p[i] != t[j]) {
j = next[j];
}
next[i] = j + 1;
}
```
KMP 算法的实现如下所示：
```c
int KMP(char* strS, char* strT) {
int i = 0;
int j = 0;
int lens = strlen(strS);
int lent = strlen(strT);
while(i < lens && j < lent) {
if(strS[i] == strT[j]) {
++i;
++j;
} else {
i = i - j + next[j];
j = next[j];
}
}
if(j == lent) {
return i - j;
} else {
return -1;
}
}
```
字符串模式匹配算法是解决字符串匹配问题的常见方法，BF 算法和 KMP 算法是其中两种常用的算法。BF 算法的时间复杂度较高，而 KMP 算法的时间复杂度较低，但需要额外的空间存储 next 数组。
VIP享7折，此内容立减4.47元 
