bugs.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 3000000
#define MAXM 4000
#define MOD 10000
char Line[MAXN];
int Hop[MAXN];
char Bug[MAXM];
int Pi[MAXM];
int Pos[MOD];
int nPos;
void Compute(int m)
{
Pi[1] = 0;
int k = 0;
for(int q = 2; q <= m; q++)
{
while((k > 0) && (Bug[k + 1] != Bug[q]))
{
k = Pi[k];
}
if(Bug[k + 1] == Bug[q])
{
k++;
}
Pi[q] = k;
}
}
void Next(int& i, int n)
{
i++;
while((i <= n) && (Hop[i]))
{
i = Hop[i];
}
Pos[nPos++ % MOD] = i;
}
void FindHops(int n, int m)
{
int q = 0;
int i = 0;
for(Next(i, n); i <= n; Next(i, n))
{
while((q > 0) && (Bug[q + 1] != Line[i]))
{
q = Pi[q];
}
if(Bug[q + 1] == Line[i])
{
q++;
}
if(q == m)
{
Hop[Pos[(nPos - (m - 0)) % MOD]] = i + 1;
if(nPos < m * 2)
{
nPos = 0;
i = 0;
q = 0;
}
else
{
nPos -= m * 2;
i = Pos[nPos % MOD];
q = 0;
}
}
}
}
int main()
{
int t;
while(scanf("%d%s", &t, Bug + 1) > 0)
{
int m = strlen(Bug + 1);
for(int i = 0; i <= m; i++)
{
Pi[i] = 0;
}
Compute(m);
getchar();
for(int i = 0; i < t; i++)
{
nPos = 0;
fgets(Line + 1, MAXN, stdin);
int n = strlen(Line + 1);
for(int i = 0; i <= n; i++)
{
Hop[i] = 0;
}
FindHops(n, m);
int i = 0;
for(Next(i, n); i <= n; Next(i, n))
{
putchar(Line[i]);
}
}
}
return 0;
}