bugs.cpp

#include <iostream>
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>
 
using namespace std;
 
char text[220000], pat[2000];
int f[2000];
 
void kmpsetup (char* pat, int * f){
	int i,k,len=strlen(pat);
	for(f[0]=-1, i=1 ; i<len;i++){
			k=f[i-1];
			while(k>=0)
					if(pat[k] == pat[i-1]) break;
					else
					k=f[k];
			f[i]=k+1;
	}
}
 
void gtln(){
	string str;
	getline(cin,str);
	strcpy(text, str.c_str());
}
 
string kmpscan(char* pat,char* text, int *f){
	int i,k;
	int len=strlen(pat);
	stack<int> s;
	stack<char> out;
	s.push(0);
	out.push(text[0]);
	for(i=k=0; text[i];){
		if(k==-1){
			i++; k=0; 
		s.push(k);
		out.push(text[i]);
			}
		else if(text[i]==pat[k]){
				i++; k++;
				if(k>=len){
						for(int c=0; c<len; c++){
								s.pop();
								out.pop();
							}
						if(!s.empty())
							k=s.top();
						else k=0;
						k++;
					}
 
		s.push(k);
		out.push(text[i]);
		}else k=f[k];
	}
	string str="";
	stack<char> out2;
	while(!out.empty()){	
		out2.push(out.top());
		out.pop();
	}
	while(!out2.empty()){	
		str+=out2.top();
		out2.pop();
	}
	return str;
}
 
 
 
int main(){
	int n;	
	while(cin>>n>>pat){
			cin.get();
			kmpsetup(pat,f);
			for(;n>0;n--){
					gtln();
					cout<<kmpscan(pat,text,f)<<endl;
			}
	}
	return 0;
}