C語言字符串的模式匹配之BF與KMP
更新時間：2021年09月10日 14:43:00 作者：Stay--hungry
這篇文章記錄一下串里面的模式匹配，模式匹配，顧名思義就是給定一個被匹配的字符串，然后用一個字符串模式（模型）去匹配上面說的字符串，看后者是否在前者里面出現。常用的有2種算法可以實現，下面我們來具體探討下
確定一個子串（模式串）在主串中第一次出現的位置。
BF算法（Brute-Force算法）
BF算法即樸素的簡單匹配法，采用的是窮舉的思路。從主串的每一個字符開始依次與模式串的字符進行比較。
int index_BF(SeqString S, SeqString T, int begin)//從S的第begin位（下標）開始進行匹配判斷
{
int i = begin, j = 0;
while (i < S.length && j < T.length)
{
if (S.ch[i] == T.ch[j])
{
i ++;
j ++;//比較下一個字符
}
else
{
i = i - j + 1;
j = 0;//模式串回溯到起點
}
}
if (j == T.length) return i - T.length; //匹配成功，則返回該模式串在主串中第一次出現的位置下標
else return -1;
}
int index_BF(char S[], char T[], int beg)
{
int i = beg, j = 0;
while (i < strlen(S) && j < strlen(T))
{
if (S[i] == T[j])
{
i ++;
j ++;
}
else
{
i = i - j + 1;
j = 0;
}
}
if (i == strlen(S)) return i - strlen(T);
else return -1;
}
int main()
{
char str1[10] = "abcde";
char str2[10] = "cde";
printf("%d", index_BF(str1, str2, 0));
return 0;
}
KMP算法（快速的）
基本思想為：主串的指針 i i i不必回溯，利用已經得到前面“部分匹配”的結果，將模式串向右滑動若干個字符，繼續(xù)與主串中的當前字符進行比較，減少了一些不必要的比較。
時間復雜度為 O ( n + m )
KMP算法的核心，是一個被稱為部分匹配表(Partial Match Table)的數組。
首先要明白什么是字符串的前綴和后綴。
如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就稱B為A的前綴。例如，”Harry”的前綴包括{”H”, ”Ha”,”Har”, ”Harr”}，我們把所有前綴組成的集合，稱為字符串的前綴集合。
同樣可以定義后綴A=SB，其中S是任意的非空字符串，那就稱B為A的后綴，例如，”Potter”的后綴包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后綴組成的集合，稱為字符串的后綴集合。
要注意的是，字符串本身并不是自己的前綴或后綴。
PMT中的值是字符串的前綴集合與后綴集合的交集中最長元素的長度。
比如，對于字符串”ababa”，它的前綴集合為{”a”, ”ab”, ”aba”, ”abab”}，它的后綴集合為{”baba”, ”aba”, ”ba”, ”a”}， 兩個集合的交集為{”a”, ”aba”}，其中最長的元素為”aba”，長度為3，即該字符串在PMT表中的值為3。性質為：該字符串前3個字符與后三個字符相同。
如果模式串有 j個字符，則PMT表中就有 j 個數值。其中第一個數值總為0。
int index_KMP(SeqString S, SeqString T, int begin)//從S的第begin位（下標）開始進行匹配判斷
{
int i = begin, j = 0;
while (i < S.length && j < T.length)
{
if (j == -1 || S.ch[i] == T.ch[j])
{
i ++;
j ++;
}
else j = next[j];//即PMT[j-1]
}
if (j == T.length) return i - T.length; //匹配成功，則返回該模式串在主串中第一次出現的位置下標
else return -1;
}
那么該如何求出next數組呢？
其實，求next數組的過程完全可以看成字符串匹配的過程，即以模式字符串為主字符串，以模式字符串的前綴為目標字符串，一旦字符串匹配成功，那么當前的next值就是匹配成功的字符串的長度。
具體來說，就是從模式字符串的第一位(注意，不包括第0位)開始對自身進行匹配運算。 在任一位置，能匹配的最長長度就是當前i位置的next值。如下圖所示。
void GetNext(SeqString T, int next[])
{
next[0] = -1;
int j = 0, k = -1;//起始時k落后j一位
while (j < T.length)//j遍歷一遍模式串，對于每個字符得到該位置的next數組的值
{
if (k == -1 || T.ch[j] == T.ch[k])
{
j ++;
next[j] = k + 1;//將j視為指向一個子串（后綴）結束后的下一個字符，k指向一個子串（前綴）的最后一個字符，則這兩個子串的重疊部分的長度（k下標從0開始）即PMT[j-1]的值
k ++;
/*也可以簡便地寫為（易記）：
j ++;
k ++;
next[j] = k;
最簡單的形式為：
next[++ j] = ++ k;
*/
}
else k = next[k];//k回溯，即將第二個子串（右滑）（減小匹配的前綴長度）
}
}
即：
#include <stdio.h>
#include <string.h>
int next[10];//全局數組
void GetNext(char T[])
{
int j = 0, k = -1;
next[0] = -1;
while (j < strlen(T))
{
if (k == -1 || T[j] == T[k])
{
j ++;
next[j] = k + 1;
k ++;
}
else k = next[k];
}
}
int index_KMP(char S[], char T[], int begin)//從S的第begin位（下標）開始進行匹配判斷
{
int i = begin, j = 0;
while (i < strlen(S) && strlen(T))
{
if (j == -1 || S[i] == T[j])
{
i ++;
j ++;
}
else j = next[j];//即PMT[j-1]
}
if (j == strlen(T)) return i - strlen(T); //匹配成功，則返回該模式串在主串中第一次出現的位置下標
else return -1;
}
int main()
{
char str1[10] = "abcde";
char str2[10] = "cde";
GetNext(str2);
printf("%d", index_KMP(str1, str2, 0));
return 0;
}
求next數組的方法也可進行優(yōu)化：
void GetNextVal(SeqString T, int nextval[])
{
nextval[0] = -1;
int j = 0, k = -1;
while (j < T.length)
{
if (k == -1 || T.ch[j] == T.ch[k])
{
j ++;
k ++;
if (T.ch[j] != T.ch[k])
nextval[j] = k;
else
nextval[j] = nextval[k];
}
else k = nextval[k];
}
}
即：
int nextval[10];//全局數組
void GetNextVal(char T[])
{
int j = 0, k = -1;
nextval[0] = -1;
while (j < strlen(T))
{
if (k == -1 || T[j] == T[k])
{
j ++;
k ++;
if (T[j] != T[k]) nextval[j] = k;
else nextval[j] = nextval[k];
}
else k = nextval[k];
}
}
int index_KMP(char S[], char T[], int begin)//從S的第begin位（下標）開始進行匹配判斷
{
int i = begin, j = 0;
while (i < strlen(S) && strlen(T))
{
if (j == -1 || S[i] == T[j])
{
i ++;
j ++;
}
else j = nextval[j];
}
if (j == strlen(T)) return i - strlen(T); //匹配成功，則返回該模式串在主串中第一次出現的位置下標
else return -1;
}
int main()
{
char str1[10] = "abcde";
char str2[10] = "bcde";
GetNextVal(str2);
printf("%d", index_KMP(str1, str2, 0));
return 0;
}
KMP—yxc模板
字符串從數組下標1開始存
#include <iostream>
using namespace std;
const int M = 1000010, N = 100010;
char S[M], p[N];
int ne[N]; //全局變量數組，初始化全為0
int main()
{
int m, n;
cin >> m;
for (int i = 1; i <= m; i ++) cin >> S[i];
cin >> n;
for (int i = 1; i <= n; i ++) cin >> p[i];//主串與模式串均由數組下標1開始存儲
// 也可以簡寫為 cin >> m >> S + 1 >> n >> p + 1;
for (int i = 2, j = 0; i <= n; i ++)//求模式串各字符處的next值，即求串p[1~i]的前后綴最大交集的長度
{ //由于字符串由下標1開始存儲，next[i]+1也是模式串下次比較的起始下標
while (j && p[i] != p[j + 1]) j = ne[j];//記錄的最大交集的長度減小，直到為0，表示p[1~i]前后綴無交集
if (p[i] == p[j + 1]) j ++;//該位匹配成功
ne[i] = j;//j即該位的ne值
}
for (int i = 1, j = 0; i <= m; i ++)//遍歷一遍主串
{
while (j && S[i] != p[j + 1]) j = ne[j];//不匹配且并非無路可退，則j后滑。j==0意味著當前i所指的字符與模式串的第一個字符都不一樣，只能等該輪循環(huán)結束i++，之后再比較
if (S[i] == p[j + 1]) j ++;//該位匹配成功
if (j == n)//主串與模式串匹配成功
{
cout << i - n << ' ';//匹配時，輸出 模式串首元素在主串中的下標
j = ne[j];//j后滑，準備繼續(xù)尋找下一個匹配處
}
}
return 0;
}
字符串從數組下標為開始存
const int N = 1000010;
char s[N], p[N];
int ne[N];
int main()
{
int n, m;
cin >> m >> p >> n >> s;
ne[0] = -1;//ne[0]初始化為-1
for (int i = 1, j = -1; i < m; i ++ )//從模式串的第2位2開始求next值
{
while (j != -1 && p[j + 1] != p[i]) j = ne[j];
if (p[j + 1] == p[i]) j ++ ;
ne[i] = j;
}
for (int i = 0, j = -1; i < n; i ++ )//遍歷一遍主串
{
while (j != -1 && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m - 1)//掃描到模式串結尾，說明匹配完成
{
cout << i - j << ' ';
j = ne[j];
}
}
return 0;
}
總結
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關注腳本之家的更多內容！
相關文章
這篇文章主要介紹了C++中實現隊列類鏈式存儲與棧類鏈式存儲的代碼示例,通過注釋來說明,直接上代碼，簡單粗暴XD 需要的朋友可以參考下2016-03-03
這篇文章主要介紹了C++中指針和引用的區(qū)別，有需要的朋友可以參考一下2014-01-01
bind是一組用于函數綁定的模板。在對某個函數進行綁定時，可以指定部分參數或全部參數，也可以不指定任何參數，還可以調整各個參數間的順序。這篇文章主要介紹了c/c++ 標準庫 bind 函數 ,需要的朋友可以參考下2018-09-09
這篇文章主要介紹了C語言實現矩陣翻轉(上下翻轉、左右翻轉)的相關資料,需要的朋友可以參考下2017-05-05
這篇博客，我們詳細講述如何利用tinyxml操縱xml。以及在操作的過程中，我們應該注意的問題2013-01-01
這篇文章主要介紹了C++實現LeetCode(107.二叉樹層序遍歷之二),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
這篇文章主要和大家分享三個可以Matlab中更簡便實現同步子圖視角的技巧，文中的示例代碼講解詳細，感興趣的小伙伴可以學習一下2022-06-06
這篇文章主要介紹了C的|、||、&、&&、異或、~、！運算符,需要的朋友可以參考下2014-06-06
今天小編就為大家分享一篇關于用C++編寫擴展node.js(node-ffi版)，小編覺得內容挺不錯的，現在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
所謂嵌套(Nest),就是一條語句里面還有另一條語句,例如 for 里面還有 for,while 里 面還有 while,或者 for 里面有 while,while 里面有 if-else,這都是允許的2022-05-05