模式匹配是數據結構中字元串的一種基本運算，給定一個子串，要求在某個字元串中找出與該子串相同的所有子串，這就是模式匹配。
概念,常見模式匹配算法,樸素的模式匹配算法,KMP匹配算法,BM匹配算法,代碼實現,
概念
模式匹配是數據結構中字元串的一種基本運算，給定一個子串，要求在某個字元串中找出與該子串相同的所有子串，這就是模式匹配。
假設P是給定的子串，T是待查找的字元串，要求從T中找出與P相同的所有子串，這個問題成為模式匹配問題。P稱為模式，T稱為目標。如果T中存在一個或多個模式為P的子串，就給出該子串在T中的位置，稱為匹配成功；否則匹配失敗。
常見模式匹配算法
樸素的模式匹配算法
算法思想：從目標串的的第一個字元起與模式串的第一個字元比較，若相等，則繼續對字元進行後續的比較，否則目標串從第二個字元起與模式串的第一個字元重新比較，直至模式串中的每個字元依次和目標串中的一個連續的字元序列相等為止，此時稱為匹配成功，否則匹配失敗。
若模式子串的長度是m,目標穿的長度是n，這時最壞的情況是每遍比較都在最後出現不等，即沒變最多比較m次，最多比較n-m+1遍，總的比較次數最多為m(n-m+1)，因此樸素的模式匹配算法的時間複雜度為O(mn)。樸素的模式匹配算法中存在回溯，這影響到匹配算法的效率，因而樸素的模式匹配算法在實際套用中很少採用。在實際套用主要採用無回溯的匹配算法，KMP算法和BM算法均為無回溯的匹配算法。
KMP匹配算法
Knuth-Morris-Pratt算法（簡稱KMP），是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一個改進算法，消除了樸素的模式匹配算法中回溯問題，完成串的模式匹配。
算法思想：
設目標串為s，模式串為t， i、j 分別為指示s和t的指針，i、j的初值均為0。
若有 si = tj，則i和j分別增1；否則，i不變，j退回至j=next[j]的位置 ( 也可理解為串s不動，模式串t向右移動到si與tnext[j]對齊 )；
比較si和tj。若相等則指針各增1；否則 j 再退回到下一個j=next[j]的位置(即模式串繼續向右移動 )，再比較 si和tj。
依次類推，直到下列兩種情況之一：
1)j退回到某個j=next[j]時有 si = tj，則指針各增1，繼續匹配；
2)j退回至 j=-1，此時令指針各增l，即下一次比較 si+1和 t0。
記模式P的長度為m,目標T的長度為n,則KMP匹配算法的時間複雜度的分析如下：
整個匹配算法由Find()和GenKMPNext()兩部分算法組成。在Find()中包含一個循環,J的初值為0，每循環一次j的值嚴格家1，指導j等於n時循環結束，故循環執行了n次。在GenKMPNext()中，表面上有兩重循環，時間複雜度似乎為O(),其實不然，GenKMPNext()的外層循環恰好執行了m-1次；另外，j的初值為-1，外層循環中，每循環一次，j的值就加1，同時，在內層循環中j減小，但最少不會小於-1，因此內層循環中j=next[j]的語句的總的執行次數應小於或等於j的值在外層循環中被加2 的次數。即在算法GenKMPNext()結束時，j=next[j]的執行總次數小於等於m-1次。
綜上，對於長度為m的模式和長度為n的目標T的模式匹配，KMP算法的時間複雜度為O(m+n)。
BM匹配算法
BM算法是一種精確字元串匹配算法（區別於模糊匹配）。採用從右向左比較的方法，同時套用到了兩種啟發式規則，即壞字元規則 和好後綴規則 ，來決定向右跳躍的距離。BM算法的基本流程: 設文本串T，模式串為P。首先將T與P進行左對齊，然後進行從右向左比較 ，如下圖所示:
若是某趟比較不匹配時，BM算法就採用兩條啟發式規則，即壞字元規則 和好後綴規則 ，來計算模式串向右移動的距離，直到整個匹配過程的結束。
1）壞字元規則（Bad Character）：
在BM算法從右向左掃描的過程中，若發現某個字元x不匹配，則按如下兩種情況討論：
如果字元x在模式P中沒有出現，那么從字元x開始的m個文本顯然不可能與P匹配成功，直接全部跳過該區域即可。
如果x在模式P中出現，則以該字元進行對齊。
用數學公式表示，設Skip(x)為P右移的距離，m為模式串P的長度，max(x)為字元x在P中最右位置。
2）好後綴規則（Good Suffix）：
若發現某個字元不匹配的同時，已有部分字元匹配成功，則按如下兩種情況討論：
如果在P中位置t處已匹配部分P'在P中的某位置t'也出現，且位置t'的前一個字元與位置t的前一個字元不相同，則將P右移使t'對應t方才的所在的位置。
如果在P中任何位置已匹配部分P'都沒有再出現，則找到與P'的後綴P''相同的P的最長前綴x，向右移動P，使x對應方才P''後綴所在的位置。
用數學公式表示，設Shift(j)為P右移的距離，m為模式串P的長度，j 為當前所匹配的字元位置，s為t'與t的距離（以上情況i）或者x與P''的距離。
代碼實現
樸素的模式匹配算法（C語言）
#include<stdio.h>
int main()
{
char s[20];
char p[5];
printf("Please input the source string:");
scanf("%s",s);
printf("Please input the goal string:");
scanf("%s",p);
printf("The result of finding is:%d\n",Find(s,p));
}
int Find(char*s,char*p)
{
int j=0,i=0,k=0;
int r=-1;
while(r==-1&&s[i]!='\0')
{
while(p[j]==s[i]&&p[j]!='\0')
{
i++;
j++;
}
if(p[j]=='\0')
{
r=k;
}
else
{
j=0;
k++;
i=k;
}
}
return r;
}
KMP模式匹配算法（C語言）
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
FILE *fin=fopen("test.in","r");
FILE *fout=fopen("test.out","w");
char s1[200],s2[200];
int next[200];
int max(int a,int b)
{
if(a>b) return a;
return b;
}
void getnext()
{
memset(next,0,sizeof(next));
int i=-1,j=0;
next[0]=-1;
while(j<strlen(s2))
{
if(i==-1||s2[i]==s2[j]){
i++; j++;
next[j]=i;
}
else i=next[i];
}
}
int KMP()
{
int i=0,j=0,len1=strlen(s1),len2=strlen(s2);
while((i<len1)&&(j<len2))
{
if(j==-1||s1[i]==s2[j]) {j++;i++;}
else j=next[j];
}
if(j==len2) return i-len2;
else return -1;
}
int index_KMP()
{
int i=0,j=0,len1=strlen(s1),len2=strlen(s2),re=0;
while(i<len1&&j<len2)
{
if(j==-1||s1[i]==s2[j]) {i++;j++;}
else j=next[j];
re=max(re,j);
}
return re;
}
int main()
{
fscanf(fin,"%s",s1);
for(int i=1;i<=3;i++)
{
fscanf(fin,"%s",s2);
getnext();
fprintf(fout,"%d %d\n",KMP(),index_KMP());
}
return 0;
}
BM匹配算法代碼實現（C++）
// BM模式匹配算法I.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define MAX 200
using namespace std;
void get_dist(int *dist,char *t,const int lenT)
{
int i;
for(i=0;i<=MAX;i++)
dist[i] = lenT;
for(i=0;i<lenT;i++)
dist[(int)t[i]] = lenT-i-1;
}
//
int BM(char *s,char *t,int *dist,const int lenS,const int lenT)
{
int i,j,k;
i = lenT-1;
while(i<lenS)
{
j = lenT-1;
k = i;
while(j>=0&&s[k]==t[j])
{
j--;
k--;
}
if(j<0)
return i+2-lenT;
else
i = i + dist[s[k]];
}
if(i>=lenS)
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
char s[MAX],t[MAX];
int dist[MAX];
cout<<"請輸入案例的個數：";
cin>>cases;
while(cases--)
{
cout<<"請輸入主串:"<<endl;
cin>>s;
int lenS = strlen(s);
while(1)
{
cout<<"請輸入需要匹配的模式串(以0結束):"<<endl;
cin>>t;
if(!strcmp(t,"0"))
break;
int lenT = strlen(t);
get_dist(dist,t,lenT);
int pos = BM(s,t,dist,lenS,lenT);
if(pos==0)
cout<<"沒有匹配項!"<<endl;
else
cout<<"匹配的開始位置為:"<<pos<<endl;
}
}
system("pause");
return 0;
}
