牛牛和字符串的日常

牛牛和字符串的日常

KMP：

字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置，也
可以求在文本串中出现的模式串最长的前缀。

nex数组：

一般匹配字符串时，我们每一个下标为起点，依次向后找，知道不满足他们相等，复杂度为O(n*m)。nex数组的用处就是充分利用已有的信息，保证不用每次回到起点重新匹配。

匹配过程

一般过程：

scanf("%s%s",a,b);
int la=strlen(a),lb=strlen(b);
for (int i=0;i<la&&la-i>=lb;i++)
{
    bool kl=0;
    for (int j=0;j<lb;j++)
        if(a[i]!=b[j]) kl=1;

    if(kl==0) printf("%d\n",i);
}

于是KMP作用便是优化这个过程。用已知信息，尽量避免某一些操作。于是在失配的时候思考如果向右平移一位会成功吗？

S[1]S[2]S[3]S[4]S[5]S[6]S[7]S[8]S[9]
T[1]T[2]T[3]T[4]T[5]T[6]

这时候，我们假设前四个匹配成功了，然而S[5]与T[5]匹配失败，即有
T [ 1 ]==S [ 1 ] T [ 2 ]==S [ 2 ] T[ 3 ]==S [ 3 ] T [ 4 ]==S [ 4 ] T [ 5 ] != S [ 5 ]
我们非要从头开始吗？非也。利用nex数组进行平移，那么就可以避免不必要的操作

• 代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n;
int nex[N];
char s[N],l[N];

int main()
{
    memset(nex,0,sizeof(nex));

    scanf("%s",s);n=strlen(s);
    int k=0;
    for (int i=1;i<n;i++)
    {
        while(k&&s[i]!=s[k]) k=nex[k];
        if(s[i]==s[k]) k++;
        nex[i+1]=k;
    }

    int t;scanf("%d",&t);
    int ans=0;
    while(t--)
    {
        scanf("%s",l);int len=strlen(l);
        k=0;int ma=0;
        for (int i=0;i<len;i++)
        {
            while(k&&l[i]!=s[k]) k=nex[k];
            if(l[i]==s[k]) k++;
            ma=max(ma,k);
        }

        ans+=ma;
    }

    printf("%d\n",ans);

    return 0;
}

• 后话

  具体的因为最近没有复习kmp，还不能详细地写出来。大家可先参考一下一些blog