串的模式匹配算法之BF算法

68 阅读 0 评论 45 点赞

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

概述

与线性表相似，串也有两种基本存储结构，顺序存储和链式存储。但考虑到存储效率和算法的方便性，串多采用顺序存储结构。

1、串的顺序存储

1）串的定长顺序存储结构
类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。合理

这种定义方式是静态的，在编译时刻就确定了串空间的大小。而大多数情况下，串的操作是以串的整体形式参与的，串变量之间的长度相差较大，在操作中串值长度的变化也较大，这样为串变量设定固定大小的空间不尽合理。因此最好是根据实际需要，在程序执行过程中动态地分配和释放字符数组空间。

2）串的堆式顺序存储结构
在C语言中，存在一个称之为“堆”（Heap）的自由存储区，可以为每个新产生的串动态分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时为了以后处理方便，约定串长也作为存储结构的一部分（也可以通过调用size()函数来直接获取串长）。

2、串的链式存储

顺序串的插入和删除操作不方便，需要移动大量的字符。因此，可采用单链表方式存储串。由于串结构的特殊性一一结构中的每个数据元素是一个字符，则在用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。例如，图4.3( a )所示为结点大小为4（即每个结点存放4个字符）的链表，图4。3（ b ）所示为结点大小为1的链表。当结点大小大于1时，由于串长不一定是结点大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其他的非串值字符（通常“#”不属于串的字符集，是一个特殊的符号）。
为了便于进行串的操作，当以链表存储串值时，除头指针外，还可附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。

串的模式匹配算法

子串的定位运算通常称为串的模式匹配或串匹配。此运算的应用非常广泛，比如在搜索引擎、拼写检查、语言翻译、数据压缩等应用中，都需要进行串匹配。

串的模式匹配设有两个字符串S和T，设S为主串，也称为正文串，本人所写代码把它叫做母串；设T为子串，也称为模式。在母串中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串中的第一个字符在母串S中出现的位置。
著名的模式匹配算法有BF算法和KMP算法。

BF（Brute-Force）算法

最简单直观的模式匹配算法是BF算法。
模式匹配不一定从母串的第一个位置开始，可以指定母串中查找的起始位置pos。

下图是BF算法的匹配过程

在这里插入图片描述

C++代码

#include<iostream>
using namespace std;
int BF(string S,string T,int pos)
{
  	int i = pos;
	int j = 1;
	while( i <= S.size() && j <= T.size() )
	{
		if( S[i-1] == T[j-1] )
		{
			i++;
			j++;
		}
		else
		{
			i = i-j+2;//i为母串S的匹配失败的位置，j为模式串S的匹配失败的位置，i-j为S第一次匹配位置之前的长度，
			          //+2的原因是一个1是本次匹配的开始位置 ，另一个1是下一次匹配的开始位置。 
			j = 1;//模式串的下一次匹配开始位置依旧是第一个字符 
		}
	}
	if( j > T.size() )
	return i - T.size();
	return 0;
} 
int main()
{
	int pos;
	string S,T;
	while( true )
	{
		cout<<"请输入母串：";
		cin>>S;
		cout<<"请输入模式串：";
		cin>>T;
		cout<<"请输入在母串中开始寻找的位置（小于等于"<<S.size()<<"）：";
		cin>>pos;
		while ( pos > S.size() )
		{
			cout<<"请重新输入在母串中开始寻找的位置（小于等于"<<S.size()<<"）：";
			cin>>pos;
		}
		cout<<"模式串在自母串第 "<<pos<<" 位开始出现的位置为 "<<BF(S,T,pos)<<endl<<endl;
	}
}

结果

请输入母串：ksfhseurhnzfkkkksgbn,csehkbnvjrvbnsjehjvfl
请输入模式串：cs
请输入在母串中开始寻找的位置（小于等于42）：43
请重新输入在母串中开始寻找的位置（小于等于42）：44
请重新输入在母串中开始寻找的位置（小于等于42）：42
模式串在自母串第 42 位开始出现的位置为 0

请输入母串：kajfdesaiefhkebxfucsnfeksnc
请输入模式串：csn
请输入在母串中开始寻找的位置（小于等于27）：3
模式串在自母串第 3 位开始出现的位置为 19

请输入母串：krsuebrcexxxxxs,cfnu,n,bnrusnumfsbc
请输入模式串：x
请输入在母串中开始寻找的位置（小于等于35）：1
模式串在自母串第 1 位开始出现的位置为 10

请输入母串：krsuebrcexxxxxs,cfnu,n,bnrusnumfsbc
请输入模式串：x
请输入在母串中开始寻找的位置（小于等于35）：10
模式串在自母串第 10 位开始出现的位置为 10

请输入母串：krsuebrcexxxxxs,cfnu,n,bnrusnumfsbc
请输入模式串：x
请输入在母串中开始寻找的位置（小于等于35）：11
模式串在自母串第 11 位开始出现的位置为 11

请输入母串：sdhfnmkexilsncfxmaiqwncfxi
请输入模式串：mai
请输入在母串中开始寻找的位置（小于等于26）：1
模式串在自母串第 1 位开始出现的位置为 17

请输入母串：