字符串匹配BF算法和KMP算法比较

#include<iostream>
using namespace std;
int BF(char S[], char T[]) {
int i = 0, j = 0,start=0;
while (S[i]!='\0'&&T[j]!='\0') {
if (S[i] == T[j]) {         //相等的话，i，j都后移一位
i++; j++;
}
else {                        //一旦有不相等的，回溯。i回到起始位置加一，j回到模式串头
start++;
i = i - j + 1;
j = 0;
}
}
if (T[j] == '\0') return start; //也可以return i-j;
//if (S[i] == '\0') return -1;  //主串到达'\0'说明没找到
else return -1;                  //模式串没到达'\0'说明没找到
}
int main() {
char S[] = "DABCDABD";
char T[] = "ABD";
int i=BF(S, T);
if (i>=0) {
cout << "已找到，在主串下标为"<<i<<"的地方"<<endl;
}
else cout << "未找到" << endl;
return 0;
}

#include<iostream>
using namespace std;
void getNext(char *T, int *next) {
int j = -1;   //前缀
int i = 0;    //后缀
next[0] = -1;
while (i < strlen(T)) {
if (j == -1 || T[i] == T[j] ){
i++; j++;
next[i] = j;
}
else {
j=next[j];  //回溯
        }
}
}
int KMP(char S[], char T[],int *next) {
int i = 0, j = 0;
int lengthS = strlen(S);
int lengthT = strlen(T);
while (i < lengthS && j < lengthT) {
if (j== -1||S[i] == T[j]) {
i++; j++;
}
else {
j = next[j];
}
}
if (j == lengthT) return (i - j);
else return -1;
}
int main() {
char S[] = "DABCDABD";
char T[] = "ABC";
int next[100];
getNext(T,next);
int i = KMP(S, T,next);
if (i>=0) {
cout << "已找到，在母串下标为"<<i<<"的地方"<<endl;
}
else cout << "未找到" << endl;
return 0;
}