本文共 1136 字，大约阅读时间需要 3 分钟。

给出一个子串和一个母串，求子串是否在母串内出现，若有求所有开始的位置

这是一个典型的字符串匹配问题，这有很多种做法，其中之一是kmp算法（当然也可以用字符串Hash来做，但是kmp的学习有助于ac自动机的理解）。

kmp的精髓在于一个nxt数组，nxt[i]表示子串的前i位的最长后缀长度j使得这个长度为j的后缀和子串的前j位匹配（即完全相同。而在字符串匹配中两个指针i，j分别代表母串前i个字符的最长后缀长度j使得这j个字符和子串的前j个匹配，当i往后移的时候如果下一位匹配，那么直接i右移，j右移，否则的话匹配失败，j=nxt[j]，一直失败就一直退，最后一遍下来就能找到所有匹配位置 那么怎么求nxt数组呢，其实和最后的字符串匹配十分相似，做一遍就好了 例题：P3375 【模板】KMP字符串匹配 贴一波代码

#include
   
    #include
    
     char s1[1000001],s2[1000001];int len1,len2,nxt[1000001],i,j;inline void KMP(){    nxt[1]=0;    j=0;    for(i=2;i<=len2;i++)    {        while(j>0&&s2[j+1]!=s2[i])j=nxt[j];        if(s2[j+1]==s2[i])j++;        nxt[i]=j;    }    j=0;    for(i=1;i<=len1;i++)    {        while(j>0&&s2[j+1]!=s1[i])j=nxt[j];        if(s2[j+1]==s1[i])j++;        if(j==len2)        {            printf("%d\n",i-len2+1);            j=nxt[j];        }    }}int main(){    scanf("%s %s",s1+1,s2+1);    len1=strlen(s1+1),len2=strlen(s2+1);    KMP();    printf("%d",nxt[1]);    for(int i=2;i<=len2;i++)printf(" %d",nxt[i]);    return 0;}
    
   

贴两幅图便于理解

这幅图中橙色部分是完全相同的，若下一个绿色的字符相等，那么i右移以后j也右移 这幅图中，绿色和紫色不匹配，于是j=nxt[j]，然后继续，匹配成功，然后继续移动指针

kmp大致就讲完了，kmp学扎实有助于后面字符串算法ac自动机的学习

转载地址：https://blog.csdn.net/zhouyuheng2003/article/details/79343938 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！