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());
        }
    }
}