串的模式匹配-BF算法

前言

Brute-Force算法

介绍

Brute Force-暴力算法，将目标串和模式串的每个字符都进行一一比较。是最为直观的一种模式匹配算法。其性能最差，但是使用最广，因为实现简单，而且在字符串较小的情况下耗费的性能也很小。

思想

将子串的字符依次与主串的匹配头处位置开始向后匹配，若相等，则继续向后遍历，直到子串结束或不相等。若过程中两字符不相等，则从主串匹配头向后移动并且与子串重新进行匹配。

BF算法设计思想

实现

方法：用顺序存储结构实现

分析：

定义两个索引记录，分别为mainIndex与childIndex。主串与子串的匹配，我们可以用循环来迭代字符，这里是递增索引。且子串递增时主串的索引总是同时跟着递增。这里我们可以遍历子串字符时，对其两个索引进行递增。但因为子串和主串在下轮匹配时候的具体变化行为又不相同，即主串索引会递增，子串索引会回溯为0，所以我们在匹配过程中遍历主串字符时所递增的索引应当是一份新的副本（在代码中为tempIndex，临时索引，用于迭代主串字符。 ），即当轮主串与子串匹配开始时 主串的位置（在代码中为mainIndex ），简称匹配头。

以上的操作可以让子串和主串仅发生一轮的匹配，由于我们存在匹配失败的情况，所以我们需要一个外层循环，来变化匹配头的位置。如：主串为："abbcababbadd";子串为："abba"当匹配失败时候，我们无需而且也不能再从原匹配头的位置开始匹配，我们的匹配头=>mainIndex 必须要递增，即必须向后迭代主串字符。同时子串匹配索引需要回溯，即索引为0。这样依次循环，直到内层迭代两串索引的循环满足恰好子串结束，即childStr.ch[childIndex] == '\0'，循环跳出的同时返回匹配头的位置，即mainIndex+1 。

代码

#define MAXLEN 255
typedef struct
{
    char ch[MAXLEN+1];
    int length;
} Mystring;
int GetLength(Mystring charArr)
{
 return charArr.length;
}
void InitString(Mystring &str,char *charArr)
{
strcpy(str.ch,charArr);
str.length=strlen(charArr);
}
//暴力匹配算法
int Index_BF(Mystring &mainStr,Mystring &childStr,int startPos)
{
    int mainIndex;//主串的匹配头记录
    int childIndex;//子串在匹配时的索引记录
    int error=0;//错误码
    if (GetLength(mainStr)<GetLength(childStr)) return error;

    for (mainIndex; mainIndex <GetLength(mainStr); mainIndex++)
    {
        int tempIndex=mainIndex;//存储此轮匹配头的索引，用作下面匹配的遍历迭代
        childIndex=0;//子串回溯
//字符匹配且子串没结束
        while(childStr.ch[childIndex]!='\0'&&mainStr.ch[tempIndex]==childStr.ch[childIndex])
        {
            //两索引记录递增
            tempIndex++;
            childIndex++;
        }
        //子串结束
        if (childStr.ch[childIndex] == '\0') return mainIndex + 1;//返回主串的匹配头的位置
    }
    
    return error;

}

主程序-Program.cpp文件

#include <iostream>
#include "string.h"
using namespace std;
#include "stdlib.h"
#include "MyString.h"

int main()
{
    Mystring str1;
    Mystring str2;
    char constChar[] = "abbcababbadd";
    char child[]="abba";
    InitString(str1,constChar);//abba
    InitString(str2,child);//abba
    
    cout<<"MainConstChar :"<<constChar<<endl;
    cout<<"MainMystring :"<<str1.ch<<endl;
    cout<<"ChildMystring :"<<str2.ch<<endl;
    cout<<"MainString Number:"<<GetLength(str1)<<endl;
    cout<<"ChildString Number:"<<GetLength(str2)<<endl;
    cout<<"Match Pos In the MainStr: "<<Index_BF(str1,str2,1)<<endl;
    return 0;
}

OutPut

MainConstChar :abbcababbadd
MainMystring :abbcababbadd 
ChildMystring :abba        
MainString Number:12       
ChildString Number:4       
Match Pos In the MainStr: 7

如果想要指定从主串某个位置开始向后匹配，可以在mainIndex初始化时候直接赋值。

int Index_BF(Mystring &mainStr,Mystring &childStr,int startPos)
{
    int mainIndex=startPos-1;
    int childIndex;
    int error=0;
    if (GetLength(mainStr)<GetLength(childStr)||mainIndex>=GetLength(mainStr)||mainIndex<0) return error;
......
......

优化：

仔细想了下，其实用一个循环就可以解决。

思路：

我们上面用到两个循环，主要是为了让不匹配的时候匹配头向后移动。但其实我们其实在每轮结束之后，我们是能通过索引记录之间的关系，直接计算出匹配头的。如图

我们的匹配头，实际上就是当前匹配过程中主串的索引值与子串的索引值之差。相对于主串来说，子串的索引值就可以认为距离匹配头的字符间距，就是说从匹配头开始迭代了多少个元素。于是有了如下的优化：

int Index_BF_Optimize(Mystring &mainStr,Mystring &childStr,int startPos)
{
    int mainIndex=startPos-1;
    int childIndex=0;//初始化
    int error=0;
    if (GetLength(mainStr)<GetLength(childStr)||mainIndex>=GetLength(mainStr)||mainIndex<0) return error;

    while (mainIndex<GetLength(mainStr)&&childIndex<GetLength(childStr))
    {
        if(mainStr.ch[mainIndex]==childStr.ch[childIndex])
        {
            mainIndex++;//匹配过程中向后迭代
            childIndex++;
        }
        else
        {
            mainIndex=mainIndex-childIndex+1;//计算原匹配头再将匹配头后移
            childIndex=0;//回溯
        }
    }
    //三种方法都可以
    if (childIndex>=GetLength(childStr)) return mainIndex-childIndex+1;
    //if (childIndex>=GetLength(childStr)) return mainIndex-GetLength(childStr)+1;
    //if (childStr.ch[childIndex] == '\0') return mainIndex-childIndex+1;
    return error;

}

 2022/10/20 23:00 虚堂人静不闻更，独坐书床对夜灯。

明日续更KMP算法

 2022/10/25 23:00 以为KMP不会有多难，看样子我错了。

串模式匹配-KMP算法详解