BF模式匹配算法

60 阅读 0 评论 40 点赞

我是靠谱客的博主淡然月饼，最近开发中收集的这篇文章主要介绍BF模式匹配算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

串的堆式顺序存储结构

typedef struct	//串的堆式顺序存储结构
{
char*ch;	//如果是非空串，就按照指定长度分配内存，否则ch指向NULL
int length;
}HString;

BF模式匹配算法

int BFCompare(HString*parent,HString*child,int pos)
{
int i=pos;	//i用于主串parent当前位置下标，若pos不为1，则从pos位置开始匹配
int j=1;	//j用于子串child中当前位置下标
while(i<=parent->length&&j<=child->length)
{
if(parent->ch[i-1]==child->ch[j-1])
{
i++;
j++;
}
else
{
i=i-j+2;	//i回溯到上次匹配首位的下一位
j=1;	//j回溯到子串的首位
}
}
if(j>child->length)
{
return i-child->length;
}
}