GPT答：

7i24.cn

1、串的BF算法：

```c
#include <stdio.h>
#include <string.h>

int BF(char* s, char* p) {
    int i = 0, j = 0;
    int len_s = strlen(s), len_p = strlen(p);
    while (i < len_s && j < len_p) {
        if (s[i] == p[j]) {
            i++;
            j++;
        } else {
            i -= j - 1;
            j = 0;
        }
    }
    if (j == len_p)
        return i - j;
    else
        return -1;
}

int main() {
    char s[] = "hello world";
    char p[] = "world";
    
    printf("%d\n", BF(s, p));
    
	return 0; 
}
```

2、串的KMP算法：

```c
#include <stdio.h>
#include <string.h>

void getNext(char* p, int next[]) { // 计算next数组
	int i=0,j=-1,len=strlen(p);
	next[0]=-1; // 初始化next数组，-1表示不存在相同的前缀和后缀 
	while(i<len){
		if(j==-1 || p[i]==p[j]){ // 相等则继续匹配，不相等则回溯到前一个可能的位置 
			i++;
			j++;
			next[i]=j; // 将当前位置的next值设为已匹配长度（即j） 
		} else{
			j=next[j]; // 回溯到上一个可能的位置（即上一次最长公共前后缀长度） 
		}
	}
}

int KMP(char* s,char* p,int next[]){
    int i=0,j=0,len_s=strlen(s),len_p=strlen(p);
    while(i<len_s && j<len_p){
        if(j==-1 || s[i]==p[j]){ // 相等则继续匹配，不相等则回溯到前一个可能的位置 
            i++;
            j++;
        } else{
            j=next[j]; // 回溯到上一个可能的位置（即上一次最长公共前后缀长度） 
        }
    }
    if(j==len_p) return i-j; // 匹配成功，返回匹配起始位置
    else return -1; // 匹配失败
}

int main() {
	char s[] = "hello world";
	char p[] = "world";
	
	int next[strlen(p)];
	getNext(p, next);
	
	printf("%d\n", KMP(s, p, next));
	
	return 0;
}
```

3、对KMP算法进一步优化：

```c
#include <stdio.h>
#include <string.h>

void getNext(char* p, int next[]) { // 计算next数组
	int i=0,j=-1,len=strlen(p);
	next[0]=-1; // 初始化next数组，-1表示不存在相同的前缀和后缀 
	while(i<len){
		if(j==-1 || p[i]==p[j]){ // 相等则继续匹配，不相等则回溯到前一个可能的位置 
			i++;
			j++;
			if (p[i] != p[j]) { 	// 如果下一位也与模式串中当前位不同，则将i赋值为j（跳过多余比较）
				next[i]=j;
			} else {
				next[i]=next[j]; // 将当前位置的next值设为已匹配长度（即j） 
			}
		} else{
			j=next[j]; // 回溯到上一个可能的位置（即上一次最长公共前后缀长度） 
		}
	}
}

int KMP(char* s,char* p,int next[]){
    int i=0,j=0,len_s=strlen(s),len_p=strlen(p);
    while(i<len_s && j<len_p){
        if(j==-1 || s[i]==p[j]){ // 相等则继续匹配，不相等则回溯到前一个可能的位置 
            i++;
            j++;
        } else{
            j=next[j]; // 回溯到上一个可能的位置（即上一次最长公共前后缀长度） 
        }
    }
    if(j==len_p) return i-j; // 匹配成功，返回匹配起始位置
    else return -1; // 匹配失败
}

int main() {
	char s[] = "hello world";
	char p[] = "world";
	
	int next[strlen(p)];
	getNext(p, next);
	
	printf("%d\n", KMP(s, p, next));
	
	return 0;
}
```