bugs.cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
static int pi[1100];
/*void popn(string &s, int n) {
for(int i = 0; i < n; i++)
s.pop();
}*/
void compute_prefix(string &P) {
int m = P.length();
pi[1] = 0;
int k = 0;
for(int q=2; q <= m; q++) {
while(k > 0 && P[k] != P[q-1]) {
k = pi[k];
}
if(P[k] == P[q-1]) {
k = k+1;
}
pi[q] = k;
}
}
void kmp_matcher(string &T, string &P) {
int n = T.length();
int m = P.length();
int q = 0;
for (int i = 1; i <= n; i++) {
while(q > 0 && P[q] != T[i-1]) {
q = pi[q];
}
if(P[q] == T[i-1]) {
q++;
}
if(q ==m ) {
//cerr << i << " " << m << endl;
T.erase(i-m, m);
//cerr << T << endl;
n = n-m;
i -= 2*m-1;
if (i < 1) i = 0;
q = pi[q];
}
}
}
int main()
{
string pat;
uint cases;
string text;
while (cin >> cases >> pat >> ws)
{
for (uint c = 0; c < cases; ++c)
{
getline(cin, text);
kmp_matcher(text, pat);
printf("%s\n", text.c_str());
}
}
}