ololo.cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <cstring>
#include <string>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FI(i,b) FOR(i,0,b)
#define V(t) vector < t >
#define pb push_back
#define MEMS(a,b) memset((a),(b),sizeof(a))
#define U unsigned
#define LL long long
using namespace std;
U LL p[2000010];
U LL h[2000010];
char s[1010];
char cur[2000010];
char st[2000010];
int main()
{
p[0]=1;
FOR(i,1,2000010)
p[i]=p[i-1]*257;
int n;
while (scanf("%d%s",&n,&s)!=EOF)
{
gets(cur);
//printf("DEBUG\n");
//printf("%s\n",s);
U LL gh=0;
int bm=strlen(s);
FOR(i,0,bm)
gh+=p[i]*((unsigned int)s[i]);
FOR(i,0,n)
{
gets(cur);
int m=strlen(cur);
int top=0;
FOR(j,0,m)
{
U LL prev=0;
if (top)
prev=h[top-1];
st[top]=cur[j];
h[top]=prev+p[top]*((unsigned int)cur[j]);
top++;
if (top>=bm)
{
U LL curh=h[top-1];
if (top>bm)
curh-=h[top-1-bm];
U LL mn=1;
if (curh==gh*p[top-bm])
top-=bm;
}
}
st[top]=0;
printf("%s\n",st);
}
}
return 0;
}