比赛 |
20150420 |
评测结果 |
AWWWWAWWWWWWWWA |
题目名称 |
审查 |
最终得分 |
20 |
用户昵称 |
Satoshi |
运行时间 |
0.740 s |
代码语言 |
C++ |
内存使用 |
0.69 MiB |
提交时间 |
2015-04-20 10:32:08 |
显示代码纯文本
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
ifstream in("censor.in");
ofstream out("censor.out");
/*class node
{
public:
int l;
int r;
}art[100001],bob[100001];
class nobe
{
public:
bool h;
int royal;
}pob[1000001];*/
string p,s;
int n;
int next[100001]={0};
int saber=0;
/*bool com(node a,node b)
{
if(a.l<b.l)return 1;
if(a.l==b.l)
{
if(a.r<b.r)return 1;
}
return 0;
}
void mark(int count)//区间合并
{
int i,debug;
for(i=1;i<=count-1;i++)
{
if(art[i].r>=art[i+1].r)
{
art[i+1]=art[i];
continue;
}
if(art[i].r<art[i+1].l)continue;
art[i].r=art[i+1].r;
art[i+1].l=art[i].l;
}
for(i=1;i<=count-1;i++)
{
if(art[i].l==art[i+1].l)
{
debug=max(art[i].r,art[i+1].r);
art[i].r=art[i+1].r=debug;
}
if(art[i].r==art[i+1].r)
{
debug=min(art[i].l,art[i+1].l);
art[i].l=art[i+1].l=debug;
}
}
for(i=1;i<=count-1;i++)
{
if(art[i].r==art[i+1].r&&art[i].l==art[i+1].l)
{
art[i].l=-1;
art[i].r=-1;
}
}
for(i=1;i<=count;i++)
{
if(art[i].l!=-1)
{
saber++;
bob[saber].l=art[i].l-1;
bob[saber].r=art[i].r-1;
}
}
//for(i=1;i<=saber;i++)out<<bob[i].l<<' '<<bob[i].r<<endl;
}*/
int kmp()
{
int i,j;
int M=p.length();
int N=s.length();
i=j=0;
while(i<N&&j<M)
{
if(j<0||s[i]==p[j])
{
i++;
j++;
}
else j=next[j];
}
//out<<i<<' '<<M<<' '<<1<<endl;
if(j>=M)return i-M+1;
else return -1;
}
void makenext(string p)
{
int i,j;
i=0;
j=-1;
next[0]=-1;
while(i<p.length()-1)
{
if(j<0||p[i]==p[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
}
int main()
{
int i,j,o,l,r;int count=0;
in>>s;
in>>n;
for(i=1;i<=n;i++)
{
in>>p;
//out<<p<<endl;
makenext(p);
o=kmp();
if(o==-1)continue;
else
{
//count++;
l=o-1;
r=p.length();
//out<<l<<' '<<r<<endl;
s.erase(l,r);
}
}
for(i=0;i<s.length();i++)
{
out<<s[i];
}
out<<endl;
//in>>count;
//for(i=1;i<=count;i++)in>>art[i].l>>art[i].r;
//sort(art+1,art+count+1,com);
//for(i=1;i<=count;i++)out<<art[i].l<<' '<<art[i].r<<endl;
//mark(count);
/*for(i=1;i<=saber;i++)out<<bob[i].l<<' '<<bob[i].r<<endl;
for(i=1;i<=saber;i++)
{
pob[bob[i].l].h=1;
pob[bob[i].l].royal=bob[i].r+1;
}
for(i=0;i<s.length();i++)
{
if(pob[i].h)i=pob[i].royal;
out<<s[i];
}*/
//out<<endl;
return 0;
}