LeetCode Implement strStr()(朴素的字符串匹配，RK算法，KMP算法)

这次来个大整合，因为正好处理到经典的字符串匹配问题

那么也是用c语言实现，现在开始吧

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

简单的问题描述，字符串needle是否尾haystack的子字符串，是的返回索引，没有返回-1；

Plan A暴力AC（朴素的字符串匹配。-。-）没必要解释了毕竟naive算法

int strStr(char* haystack, char* needle) 
{
    if(*needle=='\0')
    {
        return 0;
    }
    int flag=0;
    int pos=-1;
    for(int i=0;*(haystack+i)!='\0';i++)
    {
        for(int j=0;*(needle+j)!='\0';j++)
        {
           if(*(haystack+i+j)!='\0')
           {
               if(*(haystack+i+j)==*(needle+j))
               {
                   flag=1;
               }
               else
               {
                   flag=0;
                   break;
               }
           }
           else
           {
               flag=0;
               break;
           }
        }
        if(flag==1)
        {
            pos=i;
            break;
        }
    }
    return pos;
    exit(0);
}

PlanB（RK算法）

它的思路确实很新颖的，想法值得我们学习

那么先简单分析一下算法，被检测串将其转换成hash（其实就是把字符转换成数字）

算法导论里说这个要用霍纳准则，ok，这bi装的beautiful，举个例子假如我们只有10个数字的字符串

检测“0123456789”中有没有“567”先把“567”转换成(（5*10+6）*10+7）然后我们要在从头开始检测对吧，012=（0*10+1）*10+2，ok他和567的转换不同，不检测

接下来要检测123怎么办，先012把高位减去变成12再乘10+3就可以了

那么我们现在要字符串检测，那么就有256个字符，“Geeks is funny”检测“funny”

先把funny转换了我们都知道字符也是数字，所以(((‘f’*256+'u')*256+'n')*256+'n')*256+'y'==(肯定是个值我没算，有兴趣可以算下）

那么我们第一个窗口得转换((('G'*256+'e')*256+'e')*256+'k')*256+'s')==（我也没算但是只要不傻都知道这两个不相等），所以这不是目标串

（即使相等也要朴素的检测）

代码怎么实现这样的计算呢？

for(int i=0;i<m;i++)

{
p=(p*256+needle[i])%101;
t=(t*256+haystack[i])%101;
}

现在目标串的长度为m，p为要检测的目标，t这里的计算算的正好是我们前面说的第一个窗口，但是大家都发现哎我们模了个101干什么的？

当m足够大的时候可能会溢出，这个时候我们模上一个质数（随便摸，模什么质数都行保证别溢出）你就不模质数都可以，调皮OK，推荐模一个质数可以减少重复的次数

（因为相等我们都是要朴素的匹配一次，所以你调皮可以，我很喜欢）

那么这里还有一个移位的问题没有交代

先计算256的m-1次方（匹配穿的长度减1）

int h=1;

for(int I=0;i<m-1;i++)

{

h=(h*256)%101;

}

ok我们算出来以后呢

带到这个里面更新

t=(256*(t-h*haystack[i])+haystack[i+m])%10;

自己算一算别光看如果觉得分开看不明白那么我就po上代码

int strStr(char* haystack, char* needle) 
{
    if(*needle=='\0')
    {
        return 0;
    }
    int h=1;
    int p=0;
    int t=0;
    int m=strlen(needle);
    int n=strlen(haystack);
    for(int i=0;i<m-1;i++)
    {
        h=(h*256)%101;
    }
    for(int i=0;i<m;i++)
    {
        p=(p*256+needle[i])%101;
        t=(t*256+haystack[i])%101;
    }
    int j=0;
    for(int i=0;i<=n-m;i++)
    {
        if(p==t)
        {
            for(j=0;j<m;j++)
            {
                if(needle[j]==haystack[i+j])
                {
                }
                else
                {
                    break;
                }
                if(j==m-1)
                {
                    return i;
                }
            }
        }
        if(i<n-m)
        {
            t=((t-haystack[i]*h)*256+haystack[i+m])%101;
            if(t<0)
            {
                t=t+101;
            }
        }
    }
    return -1;
}

最后来说一说kmp算法，这个算法网上资料很多，我这学习这个算法可以说一波三折，先小甲鱼的KMP算法的讲解（说的不错-。-，然而我还是没明白），然后各种网上资料

百度，最后在严蔚敏老师的算法和数据结构中弄明白这个问题，想用博客说清楚有点难度，这里安利一波严蔚敏老师的数据结构吧，耐心点（老师的声音让人迷之发困）

直接po上代码吧，本来还想分析一下各个算法的优劣但是图传不上去，那么这次的博客就简单点吧

int strStr(char* haystack, char* needle)
{
    if(*needle=='\0')
    {
        return 0;
    }
    int LengthOfPartten=strlen(needle);
    int *next=(int *)malloc(sizeof(int)*LengthOfPartten);
    next[0]=-1;
    int j=-1;
    int i=0;
    int LengthOfText=strlen(haystack);
    while(i<LengthOfPartten-1)
    {
        if(j==-1||needle[i]==needle[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
        {
            j=next[j];
        }
    }
    for(int i=0;i<LengthOfPartten;i++)
    {
        printf("%d\n",next[i]);
    }
    i=0;
    j=0;
    while(i<LengthOfText)
    {
        if(haystack[i]==needle[j])
        {
            if(j==LengthOfPartten-1)
            {
                return i-j;
                break;
            }
            i++;
            j++;
        }
        else
        {
            if(j==0)
            {
                i++;
            }
            else
            {
                j=next[j];
            }
        }
    }
    return -1;
}

秒客网

LeetCode Implement strStr()(朴素的字符串匹配，RK算法，KMP算法)

相关文章