蓝桥杯倒计时 41天 - KMP 算法

KMP算法

KMP���法是一种字符串匹配算法，用于匹配模式串P在文本串S中出现的所有位置。

例如S=“ababac，P=“aba”，那么出现的所有位置是13。

在初学KMP时，我们只需要记住和学会使用模板即可，对其原理只需简单理解，不要过度深究，避免把自己绕进去，可以课后自己慢慢去画图理解。

KMP算法将原本O（n2）的字符串匹配算法优化到了O（n）.其精髓在于next数组，next数组表示此时模式串下标失配时应该移动到的位置，也表示最长的相同真前后缀的长度。

例如P=“ababac”，S=“abababac”。

当匹配到i=6，j=5，P［i+1］！=S［i］时，j不会移动到1重新开始匹配，而是移动到nex［j］=3继续匹配，

则接下来i=6，j=3，有P［j+1］=S［i］，成功匹配，则i，j继续后移，直到i=8.j=6完成一次匹配，则P在S中第一次出现的位置为j-i+1=3。

计算next数组（next数组仅与模式串P有关）的方式就是用P自己去匹配自己，大家只需要掌握模板即可，暂时不要深究其原理。

char s[N],p[N];int nex[M];int n = strlen(s+1),m=strlen(p+1);//字符串下标从 1 开始nex[0]=nex[1]=0;for(int i=2,j=0;iwhile(j&&p[i]!=p[j+1])j=nex[j];if(p[i]==p[j+1])j++;//从 while 出来后要么 j=0，要么 p[i]==p[j+1]，如果匹配成果，则 j 后移nex[i]=j;//如果匹配失败就回到 j，因为此时 p[1~j]=p[i-j+1~j]或 j=0（回到最初的地方开始匹配）}while(j&&s[i]!=p[j+1])j=nex[j];if(s[i]==p[j+1])j++;if(j==m)//成功匹配一次}    scanf("%s\n%s",p+1,s+1);    int n=strlen(s+1),m=strlen(p+1);    nex[0]=nex[1]=0;    for(int i=2,j=0;i        while(j&&p[j+1]!=p[i])j=nex[j];        if(p[j+1]==p[i])j++;        nex[i]=j;    }    int res=0;    for(int i=1,j=0;i        while(j&&p[j+1]!=s[i])j=nex[j];        if(p[j+1]==s[i])j++;        if(j==m)res++;    }    cout    scanf("%s",p+1);    unsigned long m=strlen(p+1);    nex[0]=nex[1]=0;    for(int i=2,j=0;i        while(j&&p[i]!=p[j+1])j=nex[j];        if(p[i]==p[j+1])j++;        nex[i]=j;    }    int len=m-nex[m];    if(m%len==0){        cout        cout    cinn;    scanf("%s",p+1);    unsigned long m=strlen(p+1);    for(int i=2,j=0;i        while(j&&p[i]!=p[j+1])j=nex[j];        if(p[i]==p[j+1])j++;        nex[i]=j;    }    int ans=0;    for(int i=1;i    cin  n;    cin  s;    memset(ne, 0, sizeof ne);    s = " " + s;    for (int i = 2, j = 0; i         while (j && s[i] != s[j + 1])            j = ne[j];        if (s[i] == s[j + 1])            j++;        ne[i] = j;    }    vector        if (ne[i] != 0)            ans += f[ne[i]];    }    cout     ios::sync_with_stdio(false);    /*多组案例初始化*/    // int t;cint;while(t--)    solve();}