字符串的模式匹配之B-F算法

一.  简介

字符串的模式匹配问题描述如下：

设有两个字符串T和Pat，在T中查找是否有和Pat值相等的子串，则称T为目标（Target ），称Pat为模式（Pattern），称查找字符串在目标串中的匹配位置的运算为模式匹配（Pattern matching）

二. B-F算法

这个模式匹配方法由Brute 和Force 提出，所以简称为B-F算法，实现原理如下

如果T0 = P0，T1 = P1，T2 = P2，Tm-1 = Pm-1，则匹配成功，返回模式串第0个字符P0在目标串中的匹配的位置

如果在某个位置i: Ti != Pi,则将模式串Pat右移一位（不是移动位置，只是右移比较），用Pat中字符从头开始与T中字符依次比较

如此反复执行，若出现以下两种情况之一，则可以结束算法：

1.   模式串的所有字符都与目标串对应字符相等（匹配成功）
2.   Pat已经移动到最后可能与T比较的位置，但是依旧没有匹配成功，则返回-1（匹配失败）

图解如下：

通过上图我们可以得到以下规律：

• 目标串字符个数 –  模式串字符个数 = 移动次数
• 移动次数 +  1  =  比较次数
• 第N次对应了T中的第N个元素
• 每一次结束进行下一次比较的时候，P都向后移动一个位置，和T中的下一个元素开始依次比较

三.  代码实现

#include <stdio.h>
#include <string.h>
//for循环的方法解决
int bf_match(char *t, char *p)
{

    int tlen = strlen(t);
    int plen = strlen(p);
    int i, j;
    for( i = 0; i <tlen - plen + 1; i++)   //只需要比较tlen - plen + 1次
    {
        for(j = 0; j < plen; j++)
        {
            if(t[i + j] != p[j])break;

        }
        if(j == plen)
        {
            return i;
        }
    }
    return -1;
}

//While循环解决
int bf_match2(char *t,char *p)
{
    int i =0,j = 0;
    while(t[i] != 0 && p[j] != 0 )  //若t[i]和p[j]都没到结尾则继续执行（因为c语言中字符串的结尾默认添加‘\0’，ASCII码为0）
    {

        if(t[i] == p[j])//若相等，分别加1
        {
            i++;  
            j++;

        }
        else
        {
            i = i - j + 1;  
            j = 0;
        }
    }
    if(p[j] == 0)
    {
        return i-j;
    }
    else return -1;
}

int main()
{
    char *t = "what is your name?";
    char *p = "your";
    int a = bf_match(t,p);
    printf("%d\n",a);
    int b = bf_match2(t,p);
    printf("%d\n",b);
    return 0;
}
输出：
8
8