bugs.cpp

#include <cstdio>
#include <cstring>
 
using namespace std;
 
int lines;
char bug[1004];
int buglen;
int back[1004];
char line[2000004];
char buf[2000004];
int sbuf[2000004];
int bufpos;
int state;
 
 
void step(char x) {
	while (bug[state + 1] != x && state != 0) {
		state = back[state];
	}
	if (bug[state + 1] == x) {
		++state;
	}
}
 
void construct() {
	back[0] = 0;
	back[1] = 0;
	state = 0;
	for (int i = 2; i < buglen; ++i) {
		step(bug[i]);
		back[i] = state;
	}
}
 
void search() {
	bufpos = 0;
	state = 0;
 
	int i = 0;
	while (line[i] != '\0') {
		step(line[i]);
 
		buf[bufpos] = line[i];
		sbuf[bufpos] = state;
		++bufpos;
 
		if (state == buglen) {
			// found! delete
			bufpos -= buglen;
			state = sbuf[bufpos - 1];
		}
		++i;
	}
}
 
int main() {
	bug[0] = '\0';
	while (scanf("%d %s\n", &lines, bug + 1) != EOF) {
		buglen = strlen(bug + 1);
		construct();
 
		for (int i = 0; i < lines; ++i) {
			fgets(line, 2000004, stdin);
 
			search();
 
			buf[bufpos] = '\0';
			printf("%s", buf);
		}
	}
}