数据结构BF和KMP算法

BF和KMP算法过程#include<iostream> #include<string.h> using namespace std; #define N 80 void main() { char S[N],T[N]; int i,j,count=0; cout<<"请输入长串S:"; gets(S); cout<<"请输入子串T:"; gets(T); i=0;j=0; while(count!=strlen(T)&&i<(strlen(S))) { if(S[i]==T[j]) {i++;j++,count++;} else {i++;j=0;count=0;} } ### 数据结构中的BF和KMP算法 #### BF（Brute Force）算法 BF算法是一种简单的字符串匹配算法，也称为暴力匹配算法。其基本思想是将模式串T在主串S中从头开始逐个字符比较，若匹配成功则返回位置，否则继续下一轮比较。 **代码实现**: ```cpp #include<iostream> #include<string.h> using namespace std; #define N 80 void main() { char S[N], T[N]; int i, j, count = 0; cout << "请输入长串S:"; gets(S); cout << "请输入子串T:"; gets(T); i = 0; j = 0; while (count != strlen(T) && i < (strlen(S))) { if (S[i] == T[j]) { i++; j++; count++; } else { i++; j = 0; count = 0; } } if (count == strlen(T)) { cout << "子串从长串的第" << i - strlen(T) + 1 << "位开始匹配成功!" << endl; } else { cout << "字符串匹配失败!" << endl; } } ``` **算法步骤解析**: 1. **初始化**: 设置两个指针`i`和`j`，分别指向主串S和模式串T的起始位置，并初始化计数器`count`为0。 2. **匹配过程**: - 比较S[i]与T[j]是否相等： - 如果相等，则`i`、`j`同时向后移动一位，`count`加1； - 如果不等，则将`i`向后移动一位，`j`重置为0，`count`清零。 3. **终止条件**: - 当`count`等于模式串T的长度时，表示匹配成功，输出位置信息； - 若遍历完主串S仍未达到匹配条件，则输出匹配失败信息。 **时间复杂度**: 在最坏情况下，BF算法的时间复杂度为O(nm)，其中n为S的长度，m为T的长度。 #### KMP（Knuth-Morris-Pratt）算法 KMP算法是一种改进的字符串匹配算法，它通过预处理模式串来减少不必要的比较次数，从而提高搜索效率。 **代码实现**: ```cpp #include<iostream> #include<string> using namespace std; #define M 80 #define N 50 void getnext(char *t, int *next) { int k = -1, j = 0; next[0] = -1; next[1] = 0; while (j < strlen(t)) { if ((k == -1) || (t[j] == t[k])) { j++; k++; next[j] = k; } else { k = next[k]; } } } void main() { int i, j, count = 0; char S[M], T[N]; cout << "请输入长串S："; cin >> S; cout << "请输入子串T："; cin >> T; int n = strlen(T); int *next = new int[n]; getnext(T, next); for (i = 0, j = 0; i < strlen(S) && j < strlen(T); ) { if ((j == 0) || (S[i] == T[j])) { i++; j++; } else { j = next[j]; } } if (j == strlen(T)) cout << "子串从长串的第" << i - j + 1 << "位开始匹配成功!" << endl; else cout << "字符串匹配失败!" << endl; } ``` **算法步骤解析**: 1. **计算next数组**: - 定义一个next数组，记录模式串T的每个位置j对应的最长公共前后缀的长度k。 - 通过动态更新k值来构造next数组，确保在模式串内部进行尽可能多的匹配。 2. **匹配过程**: - 使用两个指针`i`和`j`分别指向主串S和模式串T的位置。 - 当S[i]与T[j]相等时，`i`和`j`均向后移动一位。 - 当不相等时，利用next数组中的信息跳过不必要的比较。 3. **终止条件**: - 如果j达到模式串T的末尾，则表示匹配成功；否则继续匹配直到遍历完整个主串S或模式串T。 **时间复杂度**: KMP算法的总时间复杂度为O(n+m)，其中n为S的长度，m为T的长度。预处理阶段的时间复杂度为O(m)，匹配阶段的时间复杂度为O(n)。 ### 总结 BF算法和KMP算法都是用于解决字符串匹配问题的有效方法。BF算法虽然简单直观，但在最坏情况下效率较低；而KMP算法通过预处理模式串来避免重复匹配，从而提高了搜索效率。在实际应用中，如果对性能有较高要求，建议使用KMP算法。