大佬求调,70分KMP板子
查看原帖
大佬求调,70分KMP板子
1093559
XenoWorld楼主2024/7/25 10:24
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define int long long
#define N 1000100
using namespace std;
int ne[N];
void get_next(string & x){
    int j=0;
    ne[0]=0;
    for(int i=1;i<x.size();i++){
        while(j>0&&x[j]!=x[i])j=ne[j-1];
        if(x[j]==x[i])j++;
        ne[i]=j;
    }
}   
bool check(string & a,string & b){
    for(int i=0,j=0;i<a.size();i++){
        while(j>0&&a[i]!=b[j])j=ne[j-1];
        if(a[i]==b[j])j++;
        if(j==b.size())return true;
    }
    return false;
}
void solve(){
    string word;
    string s;
    cin>>word>>s;
    get_next(s);
    while(check(word,s)){
        for(int i=0,j=0;i<word.size();i++){
            while(j>0&&word[i]!=s[j])j=ne[j-1];
            if(word[i]==s[j])j++;
            if(j==s.size()){
                word.erase(i-(int)s.size()+1,(int)s.size());
                j=ne[j-1];
            }
        }
    }
    cout<<word<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}
2024/7/25 10:24
加载中...