字符串匹配算法(BF和KMP)

时间：2023-01-06 23:54:24

一、BF算法 

最简单直观的模式匹配算法是BF(Brute-Fore)算法.

[算法思想]
       从主串S的第pos个字符起和模式的第一个字符进行比较,若相等,则进行逐个比较后续字符;否则从主串的下一个字符起再重新和模式的字符比较.

依次类推,直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等,则匹配成功,函数返回值为和模式T中第一个字符相等的字符在主串S中的序号,

否则称匹配不成功,函数返回值为零


[算法描述]

int Index(SString S,SString T,int pos)
{
//返回模式T在主串S中第pos个字符开始第一次出现的位置.若不存在,则返回值为0
//其中,T非空,1<=pos<=StrLength(S)
i=pos; j=1;
while(i<=S[0] && j<=T[0])/* T[0]、S[0]分别用来存储字符串T的长度和S的长度 */
{
if(S[i] == T[i])  //继续比较后继字符
{
++i;
++j;
}
else             //指针后退重新开始匹配
{
i=i-j+2;     //主串的下一个字符起再重新和模式的字符比较
j=1;
}
}
if(j>T[0])
{
return i-T[0];
}
else
{
return 0;
}
}

1)最好情况下的平均时间复杂度是O(n+m)

2)最坏情况下的平均时间复杂度是O(n*m)

来看一个例子：

[问题描述]

1204 寻找子串位置

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 青铜 Bronze

题目描述 Description
给出字符串a和字符串b，保证b是a的一个子串，请你输出b在a中第一次出现的位置。


输入描述 Input Description

仅一行包含两个字符串a和b


输出描述 Output Description

仅一行一个整数


样例输入 Sample Input

abcd bc


样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

字符串的长度均不超过100

[代码实现]

#include<iostream>
#include<string.h>
using namespace std;
int Index(const string S,const string T)
{

int i=0; int j=0;

while(S[i]&&T[j])
{
if(S[i] == T[j])  //继续比较后继字符
{
++i;
++j;

}
else             //指针后退重新开始匹配
{
i=i-j+1;     //主串的下一个字符起再重新和模式的字符比较
j=0;
}
}
int TLenth=T.length()-1;
if(j>TLenth )
{
return i-TLenth;
}
return 0;

}
int main()
{
    string a,b;
    cin>>a>>b;
    cout<<Index(a,b);
    return 0;
}

二、KMP算法

kmp算法的原理,即求出P0...Pi的最大


1.kmp算法的原理
字符串匹配是计算机的基本任务之一.
举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"
详见(我上传的KMP算法.doc)

2.next数组的求解思路
通过上文完全可以对kmp算法的原理有个清晰的了解,那么下一步就是编程实现了,其中最重要的就是如何根据待匹配的模板字符串

求出对应每一位的最大相同前后缀的长度.

 void makeNext(const char P[],int next[])
{
int q,k;                      /*q:模板字符串下标; k:最大前后缀长度*/
int m=strlen(P);              /*模板字符串长度*/
next[0]=0;
for(q=1,k=0;q<m;++q)           /*for循环,从第二个字符开始,依次计算每一个字符对应的next值*/
{
while(k>0 && P[q] != P[k]) /*递归的求出P[0]...P[q]的最大的相同的前后缀长度k*/
{
k=next[k-1];           /*不理解没关系看下面的分析,这个while循环是整段代码的精髓所在,确实不好理解*/
}
if(P[q]==P[k])             /*如果相等,那么最大相同前后缀长度加1*/
{
k++;
}
next[q]=k;
}
}

现在着重讲解一下while循环所做的工作：
1.已知前一步计算时最大相同的前后缀长度为k(k>0),即P[0]...P[k-1];
2.此时比较第k项P[k]与P[q],如图1所示
3.如果P[k]等于P[q],那么简单跳出while循环;
4.关键！如果不等,那么我们应该利用已经得到的next[0]..next[k-1]来求P[0]...P[k-1]这个子串中最大相同前后缀.
为什么要求P[0]...P[k-1]的最大相同前后缀呢? 原因在于P[k]已经和P[q]失配了,而且P[q-k]...P[q-1]又与P[0]...P[k-1]相同,
看来P[0]...P[k-1]怎么唱的子串是用不了了,那么要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]..P[j-1](j==next[k-1]),

看看它的下一项P[j]是否能和P[q]匹配.如图2所示

字符串匹配算法(BF和KMP)

[算法描述]
 
#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[])
{
int q,k;
int m=strlen(P);
next[0]=0;
for(q=1,k=0;q<m;++q)
{
while(k>0 && P[q]!= P[k])
{
k=next[k-1];
}
if(P[q]==P[k])
{
k++;
}
next[q]=k;
}
}


int kmp(const char T[], const char P[],int next[])
{
int n,m;
int i,q;
n=strlen(T);
m=strlen(P);
makeNext(P,next);
for(i=0,q=0;i<n;++i)
{
while(q>0 &&P[q]!=T[i])
{
q=next[q-1];
}
if(P[q] == T[i])
{
q++;
}
if(q==m)
{
printf("Pattern occurs with shift:%d\n",(i-m+1));
}
}
}
int main()
{
int i;
int next[20]={0};
char T[]="ababxbababcadfdsss";
char P[]="abcdabd";
printf("%s\n",T);
printf("%s\n",P);
kmp(T,P,next);
for(i=0;i<strlen(P);++i)
{
printf("%d ",next[i]);
}
printf("\n");

return 0;
}

标签：

相关文章