1.先了解下其前身BF算法
-
- BF算法思想是暴力匹配，
通过回溯的方法实现，子串在主串的定位操作称为模式匹配，而子串就是模式串。
- 具体思路：从主串的第pos（假设p为主串长度为m，t为子串长度为n,下标从0开始）个位置开始匹配，如果p[i]=t[j],则统一i++,j++
否则i回溯至i-j+1处且j=0
- 代码实现
#include <stdio.h>
#include <stdlib.h>
//BF 暴力匹配 注意：下标从0开始
int BFMatch(char *p,char *t,int pos) //*p指向主字符串,*t指向模式字符串,pos代表起始匹配位置
{
int i,j;//i为主串初始位置，j为模式串初始位置
i=pos-1,j=0;
while(i<strlen(p)&&j<strlen(t))
{
if(p[i]==t[j])//如果第p串i+1个字符和t串第j+1个字符相同，则继续匹配下一个
{
i++;
j++;
}
else//否则，主串回溯到 i-(j-1)处,j重新指向第一个位置
{
i=i-j+1;
j=0;
}
}
if(j==strlen(t)) return i-j;//如果j和t串长度相同，返回t在p中的位置
else return -1;
}
main()
{
char p[10]={'a','b','a','a','b','c','a','c'};
char t[5]={'a','b','c','a'};
int position;
position=BFMatch(p,t,1);
printf("%d",position);
}
2.KMP算法
-
- 了解了BF算法后，我们来看看其时间复杂度因为主串的i需要不断回溯，而回溯后i处的字符都需要与子串的第一个比较，所以最坏情况下T=O(m*n)，
那有没有可以避免回溯，从而减少时间复杂度呢？答案：KMP算法。
- KMP算法的改进在于，i并不需要回溯，而是利用“部分已知匹配结果”，尽可能的将模式串向右移动一段距离。具体实现如下：
-
- 有主串P长度为m，子串T长度为为n，用i代表P的下标，j代表T的下标，假设i=j=0(容易思考），如果P[i]=T[j]或者当j==-1时,则统一向后移动一位，
否则，就让j=next[j]且i不变,(next[]后文会解释)，为什么要让j=next[j]呢？因为next[j]里面装的是主串丶子串前next[j]个字符是相匹配的，既然我们知道他们相匹配，就不需要只移动一位，而是将模式串第next[j]位对准主串的第i位，也就是p[i]和T[next[j]]相匹配，这样相当于将模式串T相对于主串P右移了j-next[j]位。
- 代码实现
int KMPMatch(char *p,char *t,int *next,int pos) //*p指向主字符串,*t指向模式字符串,pos代表起始匹配位置
{
int i,j;//i为主串初始位置，j为模式串初始位置
i=pos-1;
j=0;
while(i<strlen(p)&&j<strlen(t))
{
if(p[i]==t[j]||j==-1)//当j=-1或者p[i]=p[j]，则 统一向后移一位
{
i++;
j++;
}
else //否则，把t串向后移 j-next[j]位
{
j=next[j];
}
}
if(j==strlen(t)) return i-j;//如果j和t串长度相同，返回t在p中的位置
else return -1;
}
- 现在我们知道了KMP算法，但是有一个问题：next[]数组怎么计算的呢？
- next的计算与主串是无关的，其计算是与模式串相关，这里需要引出两个术语前缀与后缀，并且寻找最大长度的前缀与最大长度的后缀相等的值K即为next[j]的值。什么是前缀，后缀呢？
- 计算最大长度前缀与最大长度后缀
- 对于长度为T0,T1,T2,…….Tj的模式串T，如果其前缀T0,T1,T2….Tk-1=Tj-k,Tj-k+1,Tj-k+2,…….Tj-1,则其最大长度为k的前后缀相同。举个例子：
- next数组的计算
- next的求法相当于将最大前后缀求出之后，将所有的值右移一位，这时第一位就会空出，这一位你可以赋一位初值，例如：让next[0]=-1
- 用代码递推next（用的是KMP算法）
-
- 当“T0,T1….Tk-1=Tj-k,Tj-k+1,…….Tj-1”,则next[j]=k。那么next[j+1]等于多少呢？
- 如果T[k]=T[j],那么next[j+1]=next[j]+1=k+1
- 如果T[k]!=T[j],有如下两种情况：
如果T[j]=T[next[k]],则next[k]=next[k]+1,
如果T[j]!=T[next[k]]，则让k一直递归，即k=next[k]。
- 代码实现
void GetNext(char *p,int next[]) //获取next[]值
{
int pLen = strlen(p);
next[0] = -1;//初始化next[0]的值为-1，便于当next[j]回溯到j=0时,p的前缀向后移一位，后缀也向后移一位
int k = -1;//k为next的值
int j = 0;//next的下标
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀,当p[j]与p[k]匹配，则统一向后移一位，next[j+1]=k+1
if (k == -1 || p[j] == p[k])
{
k++;
j++;
next[j] = k;
}
else //当p[j]!=p[k]且k！=-1 ，则将 next[k]经行递归，找到p[j]=p[k]或者k=-1
{
k = next[k];
}
}
/*printf("next的值:\n");
for(j=0;j<strlen(next);j++)
{
printf("%2d,",next[j]);
}
printf("\n");
*/
}
- KMP算法完整代码
#include <stdio.h>
#include <stdlib.h>
void GetNext(char *p,int next[]) //获取next[]值
{
int pLen = strlen(p);
next[0] = -1;//初始化next[0]的值为-1，便于当next[j]回溯到j=0时,p的前缀向后移一位，后缀也向后移一位
int k = -1;//为next赋值
int j = 0;//next的下标
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀,当p[j]与p[k]匹配，则统一向后移一位，next[j+1]=k+1
if (k == -1 || p[j] == p[k])
{
k++;
j++;
next[j] = k;
}
else //当p[j]!=p[k]且k！=-1 ，则将 next[k]经行递归，找到p[j]=p[k]或者k=-1
{
k = next[k];
}
}
/*
printf("next的值:\n");
for(j=0;j<strlen(next);j++)
{
printf("%2d,",next[j]);
}
*/
}
int KMPMatch(char *p,char *t,int *next,int pos) //*p指向主字符串,*t指向模式字符串,pos代表起始匹配位置
{
int i,j;//i为主串初始位置，j为模式串初始位置
i=pos-1;
j=0;
while(i<strlen(p)&&j<strlen(t))
{
if(p[i]==t[j]||j==-1)//当j=-1或者p[i]=p[j]，则 统一向后移一位
{
i++;
j++;
}
else //否则，把t串向后移 j-next[j]位
{
j=next[j];
}
}
if(j==strlen(t)) return i-j;//如果j和t串长度相同，返回t在p中的位置
else return -1;
}
main()
{
int i;
int next[10];
int position;
char p[10]={'a','b','a','a','b','c','a','c'};
char s[5]={'a','b','c','a'};
GetNext(s,next);
position=KMPMatch(p,s,next,1);
printf("%d",position);
}