字符串匹配算法BF

66 阅读 0 评论 44 点赞

我是靠谱客的博主温柔吐司，这篇文章主要介绍字符串匹配算法BF，现在分享给大家，希望可以做个参考。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/***字符串匹配算法***/
#include<cstring>
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255//用户可在255内定义最大长度
typedef
char SString[MAXSTRLEN+1];//0号单元存放串的长度
Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T
int i;
if (strlen(chars) > MAXSTRLEN)
return ERROR;
else {
T[0] = strlen(chars);
for (i = 1; i <=T[0]; i++)
T[i] = *(chars + i - 1);
return OK;
}
}
//算法4.1BF算法
int Index(SString S,SString T,int pos)//返回模式T在主串S中第pos个字符之后第s一次出现的位置。若不存在，则返回值为0
//其中，T非空，1≤pos≤StrLength(S)
{
int i=pos;
int j=1;
while(i<=S[0]&&j<=T[0])
{
if(S[i]==T[j])
{
++i;
++j;
}
//继续比较后继字符
else{
i=i-j+2;
j=1; //指针退回重新分配，i返回到上次匹配首位的下一位
}
}
if(j>T[0])
return i-T[0];
else
return 0;
}
int main()
{
SString S;
StrAssign(S,"bbaaabbaba") ;
SString T;
StrAssign(T,"abb") ;
cout<<"主串和子串在第"<<Index(S,T,1)<<"个字符处首次匹配n";
return 0;
}