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

Brute Force 暴力算法

## 完整代码

`#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;}`