C語言字符串的模式匹配之BF與KMP

 更新時間:2021年09月10日 14:41:41   作者: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不必回溯,利用已經得到前面“部分匹配”的結果,將模式串向右滑動若干個字符,繼續與主串中的當前字符進行比較,減少了一些不必要的比較。

時間復雜度為 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數組的方法也可進行優化:

在這里插入圖片描述

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所指的字符與模式串的第一個字符都不一樣,只能等該輪循環結束i++,之后再比較
        if (S[i] == p[j + 1]) j ++;//該位匹配成功
        if (j == n)//主串與模式串匹配成功
        {
            cout << i - n << ' ';//匹配時,輸出 模式串首元素在主串中的下標
            j = ne[j];//j后滑,準備繼續尋找下一個匹配處
        }
    }    
    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語言中單引號和雙引號的區別(順利解決從字符串中提取IP地址的困惑)

    c語言中單引號和雙引號的區別(順利解決從字符串中提取IP地址的困

    c語言中的單引號和雙引號可是有很大區別的,使用之前一定要了解他們之間到底有什么不同,下面小編就給大家詳細的介紹一下吧,對此還不是很了解的朋友可以過來參考下
    2013-07-07
  • C語言實現三子棋

    C語言實現三子棋

    這篇文章主要為大家詳細介紹了C語言實現三子棋,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-11-11
  • 養成良好的C++編程習慣之內存管理的應用詳解

    養成良好的C++編程習慣之內存管理的應用詳解

    "養成良好的編程習慣"其實是相當綜合的一個命題,可以從多個角度、維度和層次進行論述和評判。如代碼的風格、效率和可讀性;模塊設計的靈活性、可擴展性和耦合度等等。要試圖把所有方面都闡述清楚必須花很多的精力,而且也不一定能闡述得全面。因此,本系列文章以軟件開發的基礎問題為切入點,闡述程序設計和代碼編寫方面的細節問題,以點帶面,旨在激發大家的思考與總結,希望能為大家帶來實際的幫助
    2013-05-05
  • 深入Windows下的回車是回車換行(\r\n)還是換行回車(\n\r)的詳解

    深入Windows下的回車是回車換行(\r\n)還是換行回車(\n\r)的詳解

    本篇文章對Windows下的回車是回車換行(\r\n)還是換行回車(\n\r)進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05
  • 貪吃蛇游戲C++命令行版實例代碼

    貪吃蛇游戲C++命令行版實例代碼

    這篇文章主要介紹了貪吃蛇游戲C++命令行版實例代碼,包含了常見的循環語句及相關游戲規則的判定方法,有助于更好的理解游戲設計原理,需要的朋友可以參考下
    2014-09-09
  • C++設計模式之單例模式

    C++設計模式之單例模式

    這篇文章主要介紹了C++設計模式之單例模式,本文同時給出了4種單例模式的實現代碼,需要的朋友可以參考下
    2014-09-09
  • 一篇文章帶你了解c++運算符重載

    一篇文章帶你了解c++運算符重載

    下面小編就為大家帶來一篇深入理解C++運算符重載。小編覺得挺不錯的,現在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2021-08-08
  • C++ 單鏈表的基本操作(詳解)

    C++ 單鏈表的基本操作(詳解)

    下面小編就為大家帶來一篇C++ 單鏈表的基本操作(詳解)。小編覺得挺不錯的,現在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-12-12
  • C++實現LeetCode(106.由中序和后序遍歷建立二叉樹)

    C++實現LeetCode(106.由中序和后序遍歷建立二叉樹)

    這篇文章主要介紹了C++實現LeetCode(106.由中序和后序遍歷建立二叉樹),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
    2021-07-07
  • C++實現學生成績管理系統

    C++實現學生成績管理系統

    這篇文章主要為大家詳細介紹了C++實現學生成績管理系統,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-12-12

最新評論

精品国内自产拍在线观看