bugs.cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define EPS 1e-9
#define PI 3.14159265358979
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
#define MAXT 2100000
#define MAXN 1100
int N, T;
char text[MAXT];
char s[MAXN];
int back[MAXN];
void build() {
back[0] = -1; back[1] = 0;
FOR (i, 2, N+1) {
int b = back[i-1];
while (b>-1 && s[back[b]+1]!=s[i]) {
//printf("%d\n", b);
b = back[b];
}
back[i] = b+1;
}
}
void kmp(char *t) {
int X = strlen(t);
int akt = 0;
vector<int> poz;
vector<char> znak;
FOR (i, 0, X) {
znak.push_back(t[i]);
while (akt>-1 && t[i]!=s[akt+1])
akt = back[akt];
akt++;
poz.push_back(akt);
//printf("%d\n", akt);
if (akt==N) {
FOR (i, 0, N) {
znak.pop_back();
poz.pop_back();
}
akt = poz.back();
}
}
FOR (i, 0, znak.size()) printf("%c", znak[i]);
}
bool solve() {
s[0] = '!'; if (scanf("%d %s", &T, s+1)<0) return false;
getchar(); N = strlen(s+1);
build();
FOR (i, 0, T) {
fgets(text, MAXT, stdin);
kmp(text);
}
return true;
}
int main() {
while(solve());
return 0;
}