目錄

一、BF算法（暴力算法）

二、KMP算法

三、KMP算法優化

---

一、BF算法（暴力算法）

一個一個往后匹配，匹配失敗繼續從母串下一個和頭（子串的頭）往后繼續匹配。

雖然簡單，但是需要較多的時間復雜度。

//BF算法（暴力算法）
//查找字符串位置（效率低）
//挨個匹配，不匹配的話進入下一個，繼續挨個匹配
//注：字符串的末尾自動補'\0'，用strlen()查找的長度比實際存放數據的長度多一個
#include<stdio.h>
#include<string.h>#define MAXSIZE 20//KMP查找位置
int BF(char* str, char* a)
{int i = 0, j = 0, flag = 1;for (i = 0; i < strlen(str) - 1; i++){flag = 1;for (j = 0; j < strlen(a) - 1; j++){if (str[i + j] != a[j]){flag = 0;break;}}if (flag == 1)return i;}return -1;				//查找失敗
}int main()
{int i = 0, next[MAXSIZE] = { 0 };char str[MAXSIZE] = { ' ' }, a[MAXSIZE] = { ' ' };//---------------------------------------輸入母串------------------------------------//printf("請輸入母串：\n");//輸入字符串while (str[i - 1] != '\n'){scanf_s("%c", &str[i]);i++;}//---------------------------------------輸入子串-------------------------------------//i = 0;printf("請輸入子串：\n");//輸入字符串while (a[i - 1] != '\n'){scanf_s("%c", &a[i]);i++;}printf("\n需要查找的子串位置：%d", BF(str, a));return 0;
}

二、KMP算法

KMP算法是一種查找算法，為了減少時間復雜度，而去掉前綴。

原理：母串還是按順序向后匹配，子串可以直接跳過上一匹配失敗的元素的前綴。因為前面的匹配成功后，母串和子串前面元素是一致的，子串有重復的前后綴，母串自然也會有，且都相同，就不再浪費時間去挨個匹配母串前綴-子串前綴，而是直接跳轉到母串后綴-子串前綴，那么自然是匹配的，相當于前面這些直接跳過，然后從上次失敗的元素開始往后匹配。（降低了時間復雜度）

next[]數組即存放子串每個字符前綴的數組。（其求法是難點）

//KMP算法查找字符串位置
#include<stdio.h>
#include<string.h>#define MAXSIZE 20int begin = 1;//獲取子串的next數組
void get_next(char* a, int* next)
{int j = 0, i = 1;				//j:前綴		i:后綴next[0] = 0;next[1] = 0;//獲取每一下標的next（前綴）do{if (a[j] == a[i])			//相等時，i和j都往后移動{next[++i] = ++j;}else if (j == 0)			//j==0時（上面的沒執行，a[i]和a[j]說明不相等），直接把next[i+1]賦值j，并把i向后移{next[++i] = j;}else								//回溯到上一級j = next[j];} while (i < strlen(a) - 1 - 1);
}//KMP查找位置
int KMP(char* str, char* a, int* next)
{int i = 0, j = 0, flag = 1;while (i < strlen(str) - 1){flag = 1;for (j = next[j]; j < strlen(a) - 1; j++){if (str[i + j] != a[j]){flag = 0;i += j;if (j == 0)		//第一位就不匹配了，直接往后移動i++;break;}}if (flag == 1)return i;			//查找成功}return -1;					//查找失敗
}int main()
{int i = 0, next[MAXSIZE] = { 0 };char str[MAXSIZE] = { ' ' }, a[MAXSIZE] = { ' ' };//---------------------------------------輸入母串------------------------------------//printf("請輸入母串：\n");//輸入字符串while (str[i - 1] != '\n'){scanf_s("%c", &str[i]);i++;}//---------------------------------------輸入子串-------------------------------------//i = 0;printf("請輸入子串：\n");//輸入字符串while (a[i - 1] != '\n'){scanf_s("%c", &a[i]);i++;}//獲取next數組get_next(a, next);for (i = 0; i < strlen(a) - 1; i++)printf("%d ", next[i]);//KMP查找下標printf("\n需要查找的子串位置：%d", KMP(str, a, next));return 0;
}

三、KMP算法優化

普通KMP算法缺陷：遇到前面元素有重復的情況，由于next[]數組，導致會一個個往前回溯，造成時間上的損耗。

優化KMP算法缺陷補全：遇到重復元素可以直接回溯到頭，不會造成太多時間損耗。

把原next[]數組改成了nextval[]數組（原來是回溯到j，現在直接回溯到next[j]，也即回溯到頭）

//KMP算法優化
// 普通KMP算法：如果遇到元素重復，仍然會一級一級回溯			(next[]數組)
//	優化KMP算法：直接回溯到頭（直接跳過了元素重復情況）		(nextval[]數組)
#include<stdio.h>
#include<string.h>#define MAXSIZE 100int count = 0;			//獲取計算次數（對比KMP算法和KMP優化算法）//獲取子串的nextval數組（KMP優化）
void get_nextval(char* a, int* nextval)
{int j = 0, i = 1;				//j:前綴		i:后綴nextval[0] = 0;nextval[1] = 0;count = 0;//獲取每一下標的nextval（前綴）do{if (a[j] == a[i])			//相等時，i和j都往后移動{if (a[j + 1] != a[i + 1])nextval[++i] = ++j;elsenextval[++i] = nextval[++j];}else if (j == 0)			//j==0時（上面的沒執行，a[i]和a[j]說明不相等），直接把nextval[i+1]賦值j，并把i向后移{nextval[++i] = j;}else								//回溯到上一級j = nextval[j];count++;} while (i < strlen(a) - 1 - 1);
}//獲取子串的next數組
void get_next(char* a, int* next)
{int j = 0, i = 1;				//j:前綴		i:后綴next[0] = 0;next[1] = 0;count = 0;//獲取每一下標的next（前綴）do{if (a[j] == a[i])			//相等時，i和j都往后移動{next[++i] = ++j;}else if (j == 0)			//j==0時（上面的沒執行，a[i]和a[j]說明不相等），直接把next[i+1]賦值j，并把i向后移{next[++i] = j;}else								//回溯到上一級j = next[j];count++;} while (i < strlen(a) - 1 - 1);
}//KMP查找位置
int KMP(char* str, char* a, int* nextval)
{int i = 0, j = 0, flag = 1;while (i < strlen(str) - 1){flag = 1;for (j = nextval[j]; j < strlen(a) - 1; j++){if (str[i + j] != a[j]){flag = 0;i += j;if (j == 0)		//第一位就不匹配了，直接往后移動i++;break;}}if (flag == 1)return i;			//查找成功}return -1;					//查找失敗
}int main()
{int i = 0, nextval[MAXSIZE] = { 0 };char str[MAXSIZE] = { ' ' }, a[MAXSIZE] = { ' ' };printf("----------注：請輸入長一點的**子串**才能比較出兩算法優劣----------\n");//---------------------------------------輸入母串------------------------------------//printf("請輸入母串：\n");//輸入字符串while (str[i - 1] != '\n'){scanf_s("%c", &str[i]);i++;}//---------------------------------------輸入子串-------------------------------------//i = 0;printf("請輸入子串：\n");//輸入字符串while (a[i - 1] != '\n'){scanf_s("%c", &a[i]);i++;}//獲取nextval數組并對比KMP算法優劣get_nextval(a, nextval);printf("KMP優化:%d\n", count);get_next(a, nextval);printf("KMP    :%d\n", count);//KMP查找下標printf("\n需要查找的子串位置：%d", KMP(str, a, nextval));return 0;
}

總結

以上是生活随笔為你收集整理的数据结构与算法（5）字符串（BF算法、KMP算法及KMP算法优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。