Go to diff to previous submission
#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; q = pi[q]; if (i < 1) { i = 0; q = 0; } } } } int main() { string pat; uint cases; string text; while (cin >> cases >> pat) { getchar(); for (uint c = 0; c < cases; ++c) { text = ""; getline(cin, text); kmp_matcher(text, pat); printf("%s\n", text.c_str()); } } return 0; }