判断两个串之间是否存在主串与子串的关系，这个过程称为串的模式匹配。
- 在串的模式匹配过程，子串 T 通常被叫做“模式串”。
普通的模式匹配（“BF”算法）
判断两个串是否存在子串与主串的关系，最直接的算法就是拿着模式串，去和主串从头到尾一一比对，这就是“BF”算法的实现思想。
将提供的模式串（例如 “abcac” ）从主串的第一个字符开始，依次判断相同位置的字符是否相等，如果全部相等，则匹配成功；反之，将子串向后移动一个字符的位置，继续与主串中对应的字符匹配。
算法运行过程：（图中，i 和 j 表示匹配字符在数组中的位置下标）
如图所示，第一次匹配，模式串和主串匹配到第三个字符时，匹配失败；模式串向右移动一个字符的位置，还是从第一个字符 ‘a’ 和主串的第二个字符 ‘b’ 相匹配，匹配失败；模式串继续后移一个字符的位置，继续匹配。
#include <stdio.h>
#include <string.h>
int sel(char * S,char *T){
int i=0,j=0;
while (i<strlen(S) && j<strlen(T)) {
if (S[i]==T[j]) {
i++;
j++;
}else{
i=i-j+1;
j=0;
}
}
//跳出循环有两种可能，i=strlen(S)说明已经遍历完主串；j=strlen(T),说明模式串遍历完成，在主串中成功匹配
if (j==strlen(T)) {
return i-strlen(T)+1;
}
//运行到此，为i==strlen(S)的情况
return 0;
}
int main() {
int add=sel("ababcabcacbab", "abcac");
printf("%d",add);
return 0;
}
时间复杂度
“BF” 算法在最理想的情况下的时间复杂度为O(m)( m 是模式串的长度，也就是第一次匹配就成功的情况)。
一般情况下，"BF"算法的时间复杂度为O(n+m)(n是主串的长度，m是模式串的长度)。
最坏的情况下的时间复杂度为O(nm)（例如主串 S 为“000000000001”，模式串 T ”001”,每次匹配时，直到匹配最后一个元素，才得知匹配失败，运行了 nm 次）。
KMP算法
串的普通模式匹配算法，大体思路是：模式串从主串的第一个字符开始匹配，每匹配失败，主串中记录匹配进度的指针 i 都要进行 i-j+1 的回退操作（这个过程称为“指针回溯”），同时模式串向后移动一个字符的位置。一次次的循环，直到匹配成功或者程序结束。
"KMP"算法相比于"BF"算法，优势在于：
在保证指针 i 不回溯的前提下，当匹配失败时，让模式串向右移动最大的距离；
并且可以在O(n+m)的时间数量级上完成对串的模式匹配操作；
故，"KMP"算法称为“快速模式匹配算法”。
next函数实现
#include <stdio.h>
#include <string.h>
void Next(char*T,int *next){
int i=1;
next[0]=0;
int j=0;
while (i<strlen(T)) {
if (j==0||T[i-1]==T[j-1]) {
i++;
j++;
next[i]=j;
}else{
j=next[j];
}
}
}
