更新时间：2024-07-11 12:42
模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。
模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。
假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T称为目标。如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败。
算法思想：从目标串的的第一个字符起与模式串的第一个字符比较，若相等，则继续对字符进行后续的比较，否则目标串从第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。
若模式子串的长度是m,目标串的长度是n，这时最坏的情况是每遍比较都在最后出现不等，即每遍最多比较m次，最多比较n-m+1遍，总的比较次数最多为m(n-m+1)，因此朴素的模式匹配算法的时间复杂度为O(mn)。朴素的模式匹配算法中存在回溯，这影响到匹配算法的效率，因而朴素的模式匹配算法在实际应用中很少采用。在实际应用主要采用无回溯的匹配算法，KMP算法和BM算法均为无回溯的匹配算法。
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算法的基本流程: 设文本串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
int main()
{
char s[20];
char p[5];
}
int Find(char*s,char*p)
{
int j=0,i=0,k=0;
int r=-1;
{
{
i++;
j++;
}
{
r=k;
}
else
{
j=0;
k++;
i=k;
}
}
return r;
}
KMP模式匹配算法（C语言）
#include
#include
#include
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 { 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 { 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 { if(j==-1||s1[i]==s2[j]) {i++;j++;} else j=next[j]; re=max(re,j); } return re; } int main() { for(int i=1;i<=3;i++) { getnext(); } return 0; } BM匹配算法代码实现（C++） // BM模式匹配算法I.cpp : Defines the entry point for the console application. // #include #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 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 { 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]; cin>>cases; while(cases--) { cin>>s; int lenS = strlen(s); while(1) { cin>>t; break; int lenT = strlen(t); get_dist(dist,t,lenT); int pos = BM(s,t,dist,lenS,lenT); if(pos==0) else } } return 0; }