dalao求助!88分 WA5,8
查看原帖
dalao求助!88分 WA5,8
265978
Retired楼主2021/5/15 12:13
// Problem: P4824 [USACO15FEB]Censoring S
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4824
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e6+10,M=1e9+7;
ll n,m,_;

string s;
char p[N];
ll ne[N];

void solve()
{
	cin>>s>>p+1;n=s.size(),m=strlen(p+1);
	
	for(int i=2,j=0;i<=m;i++)
	{
		while(j&&p[i]!=p[j+1])j=ne[j];
		if(p[i]==p[j+1])j++;
		ne[i]=j;
	}	
	
	for(int i=0,j=0;i<n;i++)
	{
		while(j&&s[i]!=p[j+1])j=ne[j];
		if(s[i]==p[j+1])j++;
		if(j==m)
		{
			i-=m-1;
			s.erase(i,m);
			j=ne[j];
			i-=m+1;//需要多减一位,因为有i++
		}
		if(i<=-1)i=-1;//否则会re好多
	}
	cout<<s;
}

int main()
{
	solve();
	return 0;
}
2021/5/15 12:13
加载中...