33、串的模式匹配－Brute-Force算法

一、與串相關的概念

1、串（或字符串）是由零個或多個字符組成的有限序列。一般記作：s=〃c0c1c2…cn-1〃(n≥0)。零個字符的串稱為空串，通常以兩個相鄰的雙引號來表示空串，僅由空格組成的的串稱為空格串，如：s=〃〃；

2、串與線性表的異同。字符串一般簡稱為串，可以將它看作是一種特殊的線性表，這種線性表的數據元素的類型總是字符型的，字符串的數據對象約束為字符集。在線性表的基本操作中，大多以“單個元素”作為操作對象，而在串中，則是以“串的整體”或一部分作為操作對象。因此，線性表和串的操作有很大的不同。

3、當兩個串的長度相等且各對應位置上的字符都相同時，這兩個串是相等的。串中任意個連續字符組成的序列稱為該串的子串。包含子串的串被稱為主串。

4、模式匹配：子串定位運算稱為模式匹配()或串匹配()。模式匹配成功是指在目標串s中找到一個模式串t；模式匹配不成功則指目標串s中不存在模式串t。在串匹配中，一般將主串稱為目標串，子串稱之為模式串。

二、串的幾種表示方法

1、順序存儲結構（靜態）

分配一組地址連續的存儲單元存放串值的字符序列。

String[+1];

串的模式匹配算法實驗心得_串匹配算法的基本含義_串的模式匹配算法是指

2、串的塊鏈存儲表示

塊，一組連續的字符。塊鏈存儲表示，把串分成指定等長的塊，每一塊用一個結點表示，把各塊鏈成一個鏈表。當一個結點不滿時，用特殊字符（如‘#’）填充。若塊的長度為1，就是以單字符為結點的鏈表結構。

#;//定義結點的大小

{//結點結構

charstr[];

*next;

}Lstring;

塊的大小與存儲密度有關：

串的模式匹配算法實驗心得_串匹配算法的基本含義_串的模式匹配算法是指

3、堆分配存儲表示（常用）

堆存儲結構的特點是，仍以一組空間足夠大的、地址連續的存儲單元存放串值字符序列，但它們的存儲空間是在程序執行過程中動態分配的。所以也稱為動態存儲分配的順序表。每當產生一個新串時，系統就從剩余空間的起始處為串值分配一個長度和串值長度相等的存儲空間。

在C語言中，存在一個稱為“堆”的自由空間，由動態分配函數malloc()分配一塊實際串長所需的存儲空間，如果分配成功，則返回這段空間的起始地址，作為串的基址。由free()釋放串不再需要的空間。

C語言對堆分配存儲結構的定義如下：

{

char*str;

;

}Hstring;

串匹配算法的基本含義_串的模式匹配算法是指_串的模式匹配算法實驗心得

三、Brute-Force算法的思想

Brute-Force算法的基本思想是：從目標串s的第一個字符起和模式串t的第一個字符進行比較，若相等，則繼續逐個比較后續字符，否則從串s的第二個字符起再重新和串t進行比較。依此類推，直至串t中的每個字符依次和串s的一個連續的字符序列相等，則稱模式匹配成功，此時串t的第一個字符在串s中的位置就是t在s中的位置，否則模式匹配不成功。

串的模式匹配算法是指_串匹配算法的基本含義_串的模式匹配算法實驗心得

串的模式匹配算法是指_串的模式匹配算法實驗心得_串匹配算法的基本含義

四、Brute-Force算法的C語言描述

串的模式匹配算法實驗心得_串的模式匹配算法是指_串匹配算法的基本含義

五、Brute-Force算法的C語言實現

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

#include"ctype.h"

串的模式匹配算法實驗心得_串匹配算法的基本含義_串的模式匹配算法是指

;//Status是函數的類型,其值是函數結果狀態代碼，如OK等

;//Boolean是布爾類型,其值是TRUE或false

#//數據元素個數

#//關鍵字的最大長度

#E10//存儲空間初始分配量

#2//存儲空間分配增量

char*ch;

;

}HString;

(HString&T)

{//初始化(產生空串)字符串T

T.length=0;

T.ch=NULL;

}//

(HString&T,char*chars)

{//生成一個其值等于串常量chars的串T

inti,j;

if(T.ch)

free(T.ch);//釋放T原有空間

i=strlen(chars);//求chars的長度i

if(!i)

{//chars的長度為0

T.ch=NULL;

T.length=0;

}//if

else

T.ch=(char*)malloc(i*sizeof(char));//分配串空間

if(!T.ch)exit(-1);//失敗

for(j=0;j

T.ch[j]=chars[j];

T.length=i;

}//else

;

}//

(HString&T)

inti;

for(i=0;i

printf("%c",T.ch[i]);

printf("\n");

}//

(,,intpos)

inti,j;

串匹配算法的基本含義_串的模式匹配算法是指_串的模式匹配算法實驗心得

i=pos;//指向串s的第1個字符

j=0;//指向串t的第1個字符

while((i

if(s.ch[i]==t.ch[j])//比較兩個子串是否相等

{++i;//繼續比較后繼字符

++j;

}//if

else

i=i-j+1;//串s指針回溯重新開始尋找串t，注意，在算法中我們的存儲結構是數組，我//們在此實現中，采用的是堆，導致語句有點小不一樣。

j=0;

}//else

if(j>=t.length)return(i-t.length+1);//匹配成功，返回模式串t在串s中的起始位置

;//匹配失敗返回0

(HString&t)

printf("串t為:");

(t);

}//

(HString&s)

charch[80];

printf(":\n");

scanf("%s",ch);

(s,ch);

}//InputS

intmain()

inti,pos=1;

,s;

(s);//由于HSring定義了指針，所以必須初始化

(t);

InputS(s);

InputS(t);

(s);

(t);

i=Index(s,t,pos);

printf(":%d\n",i);

return1;

六、Brute-Force算法的復雜度分析

最好的情況：算法時間復雜度為：O（Strlen(T)）;

最壞的情況：算法時間復雜度為：O（Strlen(S)×Strlen(T)）。

在線咨詢

上一篇：微視短視頻自動引流腳本附視頻教程
下一篇：外貿溝通技巧：用WhatsApp與國外客戶聊天的秘訣及封號解決方法

您的項目需求

*請認真填寫需求信息，我們會在24小時內與您取得聯系。

整合營銷服務商

33、串的模式匹配－Brute-Force算法

您的項目需求