题目链接

https://ac.nowcoder.com/acm/contest/7412/G

题目大意

字符串匹配。

解题思路

我的KMP详讲更新于2020.10.21
一上来就想暴力，明知道暴力不行，还是想试试，毕竟不会别方法了。果不其然，过了80多的数据，没AC。
正解：KMP！（没听说过，百度了一下，发现真的是巨难！用了3h才勉强理解，但是代码还是自己写不出来，背过的）
（我实在讲不明白，直接放弃自己手写）
（教会我KMP的大佬讲解）
就本题而言，无非是把牛牛喜欢的字符串S作为模式串（即由j控制的字符串），多组输入的字符串作为文本串（即由i控制的字符串），同时在KMP函数里统计一下匹配到的最长子串，对应语句为 maxx=max(maxx,j);，理解了KMP实现过程之后会发现j的值为公共子串的长度，所以取j的最大值就是能扫描到的模式串S（即牛牛喜欢的字符串）的最长长度。累加输出。

函数模板

//获取next数组
void getnext(string s){
    nxt[0]=-1;//不能用next作为名字，因为c++中存在next
    int i=0,j=-1;
    int len=s.length();
    while(i<len-1){
        if(j==-1 || s[i]==s[j]){
            ++i;
            ++j;
            nxt[i]=j;
        }
        else j=nxt[j];    
    }    
}
//KMP，只是匹配的过程（根据题目要求进行变形）
void KMP(string s,string p){
    int i=0,j=0,maxx=0;
    int slen=s.length(),plen=p.length();
    while(i<slen && j<plen){
        if(j==-1 || s[i]==p[j]){
            ++i;
            ++j;
        }
        else j=nxt[j];
    }
}

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int nxt[N];
void getnext(string s){
    nxt[0]=-1;
    int i=0,j=-1;
    int len=s.length();
    while(i<len-1){
        if(j==-1 || s[i]==s[j]){
            ++i;
            ++j;
            nxt[i]=j;
        }
        else j=nxt[j];    
    }    
}
int KMP(string s,string p){
    int i=0,j=0,maxx=0;
    int slen=s.length(),plen=p.length();
    while(i<slen && j<plen){
        if(j==-1 || s[i]==p[j]){
            ++i;
            ++j;
            maxx=max(maxx,j);//唯一变化！关键语句！
        }
        else j=nxt[j];
    }
    return maxx;
}

ll ans;
string str,tmpstr;
int n;
int main(){
    cin>>str;
    getnext(str);
    cin>>n;
    while(n--){
        cin>>tmpstr;
        ans+=KMP(tmpstr,str);
    }
    cout<<ans<<endl;
}

优化代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int nxt[N];
/*
void CreateNext(string p){
    nxt[1]=0;
    int i=1,j=0,len=p.size();
    p='.'+p;
    while(i<=len){
        if(j==0 || p[i]==p[j]){
            ++i,++j;
            nxt[i]=j;
        }
        else j=nxt[j];
    }
}
*/
void CreateNext(string p){
    nxt[1]=0;
    int i=1,j=0,len=p.size();
    p='.'+p;
    while(i<=len){
        if(j==0 || p[i]==p[j]){//通过i去更新nxt里面存储的位置 
            ++i;++j;
            if(p[i]==p[j]) nxt[i]=nxt[nxt[i]];//此时nxt[i]=j，因此 <=> nxt[i]=nxt[j];
            else nxt[i]=j;
        }
        else j=nxt[j];
    }
}
int Match(string s,string p){
    int i=1,j=1,happy=0,slen=s.size(),plen=p.size();
    s='.'+s;
    p='.'+p;
    while(i<=slen && j<=plen){
        if(j==0 || s[i]==p[j]) {happy=max(happy,j);++i;++j;}
        else j=nxt[j];
    }
//    cout<<happy<<endl;
    return happy;
}
string p,s;
int n,ans;
int main(){
    cin>>p>>n;
    CreateNext(p);
    for(int i=1;i<=n;i++){
        cin>>s;
        ans+=Match(s,p);
    }
    cout<<ans<<endl;
}

暴力代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<string> book;
string tmp_str,like;
int n;
ll ans;
int main(){
    cin>>like;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>tmp_str;
        book.push_back(tmp_str);
    }
    int vsize=book.size();
    int likesize=like.length();
    for(int i=0;i<vsize;i++){
        int maxx=0;
        int booksize=book[i].length();
        for(int j=0;j<booksize;j++){
            int p2=0,p1=j,cnt=0;
            while(p1<booksize && p2<likesize && book[i][p1]==like[p2]) p1++,p2++,cnt++;
            maxx=max(cnt,maxx);
        }
        ans+=maxx;
    //    cout<<maxx<<endl;    
    }
    cout<<ans<<endl;
}