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){ s.push(k); out.push(text[i]); i++; k=0; } else if(text[i]==pat[k]){ s.push(k); out.push(text[i]); i++; k++; if(k>=len){ for(int c=0; c<len; c++){ s.pop(); out.pop(); } if(!s.empty()){ k=s.top(); k++; } else k=0; } }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; }
--- c4.s1263.cteam016.bugs.cpp.0.bugs.cpp +++ c4.s1297.cteam016.bugs.cpp.0.bugs.cpp @@ -33,13 +33,15 @@ stack<int> s; stack<char> out; - s.push(0); - out.push(text[0]); + //s.push(0); + //out.push(text[0]); for(i=k=0; text[i];){ if(k==-1){ + s.push(k); + out.push(text[i]); i++; k=0; - s.push(k); - out.push(text[i]); } else if(text[i]==pat[k]){ + s.push(k); + out.push(text[i]); i++; k++; if(k>=len){ @@ -48,12 +50,10 @@ out.pop(); } - if(!s.empty()) + if(!s.empty()){ k=s.top(); + k++; + } else k=0; - k++; } - - s.push(k); - out.push(text[i]); }else k=f[k]; }