从KMP原理原理出发解决问题

网上已经很多对具体过程的解释 我就不再赘述 这里 我只说一下 我对KMP算法的理解

ps:刚开始 也是想了好久 但是始终不得其解 后来 算法导论 出现了 正式看到了其中的思想之后 明白了这个kmp算法

KMP算法

俗称看毛片算法  它的原理是充分利用模式串的信息 
进一步来说呢就是  如果我们已经 使得文本串和模式串匹配了n个字符
而发现他们的n+1个字符不匹配  暴力匹配在这这时会 在文本串的匹配起点向下挪一位 然后使模式串匹配起点指向开头重新继续匹配                        假设有文本穿           abcabc                       
而kmp则是充分利用已有信息 如果在已经匹配的信息中 模式串abcabe  
发现前五位相等  第六位 不同  那么利用kmp的核心思想 充分利用已知信息  发现匹配的前五位中有共同前后缀ab 那么我们直接跳过模式串的ab前缀直接从c继续匹配  这时候我们就省掉了两次检查时间  如果前后缀更长  那么省2的时间将会更多。。。 

kmp算法组成

由一个next数组  和一个函数 构成  next数组是利用模式串信息构造而成

附上next数组求法

int* get_next()
{
    创建next数组  包含maxn个整形元素
    int *next=(int*)malloc(sizeof(int)*maxn);
    int i=0,j=-1;
    for(;i<=s.len;)
    {
        if(j==-1||s[i]==s[j])//s为模式串
        {
            i++;
            j++;
            next[i]=j;
        }
        else
        {
            j=next[j]; 
        }
    }
}

PS:如果看到这里 明白大致原理 但是还有那么一些模糊 推荐你去bilibili 去查 KMP算法 下面有一个汪看了也会懂的一个视频 讲解的非常透彻。
FINISHED！