串匹配之蛮力算法

基于邓俊辉老师的c++数据结构

问题描述：
给定文本串T,长度n 如：1001101101
模式串P,长度m，如： 1011
此时默认的字符集是{'1','0'}
求成功匹配的字符首位置

算法描述：
将P和T从头对齐，依次比对。一旦失败，将P右移一位，继续从头比对。

蛮力算法

代码实现：

//p:pattern模式串  T:text文本串
int match1(char* P,char* T)
{
    size_t n = strlen(T),i=0;//获得文本串的长度，设定指向文本串的指针i
    size_t m = strlen(P),j=0;//获得模式串的长度，设定指向模式串的指针j

    while(j<m && i<n)
    {
        if(T[i]==P[j])//成功匹配字符则同时向右挪一位
        {
            i++;
            j++;
        }
        else{
            i-=(j-1);//相当于i先减去j再加1，也就是在原来的位置上右移一位
            j=0;//j重新归零
        }
    }
    return i-j;//返回成功匹配的起始位置
}

复杂度分析：
从最坏情况分析，比如：
T：0000000000000000000000000000001
P : 0001
那么需要比较n-m+1轮，每轮m次 比对
当n>>m时，渐进时间复杂度是O(n*m)
但事实并不悲观。
实际上，当前字符集的个数仅仅为2，极其容易出现局部匹配。
假如字符集的数目很可观，那么将很难出现局部匹配，此时m->1
时间复杂度趋近于O(n)