0.題目

在一個主串S={a, b, c, c, b, c, a, b, d}, 模式串T={a, b, d};請找出模式串在主串中第一次出現的位置
提示: 不需要考慮字符串大小寫問題，字符均為小寫字母

第一次在7的位置匹配上

1.BF算法

Brute-Force算法，簡稱為 BF算法，是一種簡單樸素的模式匹配算法，常用于在一個主串 S 內查找一個子串 T 的出現位置。

核心思想與操作是：

對于給定的主串 S 與子串 P ，主串 S 的長度為 N，子串 T 的長度為 M ；

首先，將 S[1] 和 T[1] 進行比較；

若相等，則再比較 S[2] 和 T[2] ，一直到 T[M] 為止；

若 S[1] 和 T[1] 不等，則 T 向右移動一個字符的位置，再依次進行比較

假設主串 S="abcababca"；模式串T = "abcdex"

開始比較

對比a

對比b

對比c

匹配不上，開始回溯

只要匹配不上就開始回溯

字符串數組約定: 0位放字符串數組的長度

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0#define MAXSIZE 40 /* 存儲空間初始分配量 */ typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */ typedef int ElemType; /* ElemType類型根據實際情況而定，這里假設為int */ typedef char String[MAXSIZE+1]; /* 0號單元存放串的長度 *//* 生成一個其值等于chars的串T */ Status StrAssign(String T,char *chars) {int i;if(strlen(chars)>MAXSIZE)return ERROR;else{T[0]=strlen(chars);for(i=1;i<=T[0];i++)T[i]=*(chars+i-1);return OK;} }Status ClearString(String S) {S[0]=0;/* 令串長為零 */return OK; }/* 輸出字符串T。 */ void StrPrint(String T) {int i;for(i=1;i<=T[0];i++)printf("%c",T[i]);printf("n"); }/* 輸出Next數組值。 */ void NextPrint(int next[],int length) {int i;for(i=1;i<=length;i++)printf("%d",next[i]);printf("n"); }/* 返回串的元素個數 */ int StrLength(String S) {return S[0]; }

思路:

分別利用計數指針i和j指示主串S和模式T中當前正待比較的字符位置,i初值為pos,j的初值為1;

如果2個串均為比較到串尾,即i和j均小于等于S和T的長度時, 則循環執行以下的操作:

S[i]和T[j]比較,若相等,則i 和 j分別指示串中下一個位置,繼續比較后續的字符;

若不相等,指針后退重新開始匹配. 從主串的下一個字符串(i = i - j + 2)起再重新和模式第一個字符(j = 1)比較;

如果j > T.length, 說明模式T中的每個字符串依次和主串S找中的一個連續字符序列相等,則匹配成功,返回和模式T中第一個字符的字符在主串S中的序號(i-T.length);否則匹配失敗,返回0;

int Index_BF(String S, String T,int pos){//i用于主串S中當前位置下標值，若pos不為1，則從pos位置開始匹配int i = pos;//j用于子串T中當前位置下標值int j = 1;//若i小于S的長度并且j小于T的長度時，循環繼續while (i <= S[0] && j <= T[0]) {//比較的2個字母相等,則繼續比較if (S[i] == T[j]) {i++;j++;}else{//不相等,則指針后退重新匹配//i 退回到上次匹配的首位的下一位;//加1,因為是子串的首位是1開始計算;//再加1的元素,從上次匹配的首位的下一位;i = i-j+2;//j 退回到子串T的首位j = 1;}}//如果j>T[0],則找到了匹配模式if (j > T[0]) {//i母串遍歷的位置 - 模式字符串長度 = index 位置return i - T[0];}else{return -1;} }

2.RK算法

1.思想:把需要對比的字符串轉換成相應的哈希值

字母轉換成哈希值，將當前的字母-'a'得到的數字

比如:

a - a = 0; b - a = 1; c - a = 2; d - a = 3; e - a = 4;

2.小寫字母之間存在進制，即26進制

例如:

"cba" = 'c'*26*26 + 'b'*26 + 'a' *1= (c - a)*26^2 + (b - a)*26^1 + (a - a) *26^0= 2 * 26^2 + 1 * 26 + 0 * 1= 1352 + 26 + 0= 1378

代碼:

//d 表示進制 #define d 26//4.為了杜絕哈希沖突. 當前發現模式串和子串的HashValue 是一樣的時候.還是需要二次確認2個字符串是否相等. int isMatch(char *S, int i, char *P, int m) {int is, ip;for(is=i, ip=0; is != m && ip != m; is++, ip++)if(S[is] != P[ip])return 0;return 1; }//3.算出最d進制下的最高位 //d^(m-1)位的值; int getMaxValue(int m){int h = 1;for(int i = 0;i < m - 1;i++){h = (h*d);}return h; }/** 字符串匹配的RK算法* Author：Rabin & Karp* 若成功匹配返回主串中的偏移，否則返回-1*/ int RK(char *S, char *P) {//1. n:主串長度, m:子串長度int m = (int) strlen(P);int n = (int) strlen(S);printf("主串長度為:%d,子串長度為:%dn",n,m);//A.模式串的哈希值; St.主串分解子串的哈希值;unsigned int A = 0;unsigned int St = 0;//2.求得子串與主串中0~m字符串的哈希值[計算子串與主串0-m的哈希值]//循環[0,m)獲取模式串A的HashValue以及主串第一個[0,m)的HashValue//此時主串:"abcaadddabceeffccdd" 它的[0,2)是ab//此時模式串:"cc"//cc = 2 * 26^1 + 2 *26 ^0 = 52+2 = 54;//ab = 0 * 26^1 + 1 *26^0 = 0+1 = 1;for(int i = 0; i != m; i++){//第一次 A = 0*26+2;//第二次 A = 2*26+2;A = (d*A + (P[i] - 'a'));//第一次 st = 0*26+0//第二次 st = 0*26+1St = (d*St + (S[i] - 'a'));}//3. 獲取d^m-1值(因為經常要用d^m-1進制值)int hValue = getMaxValue(m);//4.遍歷[0,n-m], 判斷模式串HashValue A是否和其他子串的HashValue 一致.//不一致則繼續求得下一個HashValue//如果一致則進行二次確認判斷,2個字符串是否真正相等.反正哈希值沖突導致錯誤//注意細節://① 在進入循環時,就已經得到子串的哈希值以及主串的[0,m)的哈希值,可以直接進行第一輪比較;//② 哈希值相等后,再次用字符串進行比較.防止哈希值沖突;//③ 如果不相等,利用在循環之前已經計算好的st[0] 來計算后面的st[1];//④ 在對比過程,并不是一次性把所有的主串子串都求解好Hash值. 而是是借助s[i]來求解s[i+1] . 簡單說就是一邊比較哈希值,一邊計算哈希值;for(int i = 0; i <= n-m; i++){if(A == St)if(isMatch(S,i,P,m))//加1原因,從1開始數return i+1;St = ((St - hValue*(S[i]-'a'))*d + (S[i+m]-'a'));}return -1; }

使用并打印:

char *buf="abcababcabx"; char *ptrn="cabab"; printf("主串為%sn",buf); printf("子串為%sn",ptrn);int index = RK(buf, ptrn); printf("find index : %dn",index);

打印

總結

以上是生活随笔為你收集整理的对比两个字符串相等_字符串匹配问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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