Go to diff to previous submission
#include <iostream> #include <stack> #include <string> #include <cstring> #include <cstdio> using namespace std; char text[2200000], 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; }