Source code for submission s1297

Go to diff to previous submission

bugs.cpp

  1. #include <iostream>
  2. #include <stack>
  3. #include <string>
  4. #include <cstring>
  5. #include <cstdio>
  6.  
  7. using namespace std;
  8.  
  9. char text[2200000], pat[2000];
  10. int f[2000];
  11.  
  12. void kmpsetup (char* pat, int * f){
  13. int i,k,len=strlen(pat);
  14. for(f[0]=-1, i=1 ; i<len;i++){
  15. k=f[i-1];
  16. while(k>=0)
  17. if(pat[k] == pat[i-1]) break;
  18. else
  19. k=f[k];
  20. f[i]=k+1;
  21. }
  22. }
  23.  
  24. void gtln(){
  25. string str;
  26. getline(cin,str);
  27. strcpy(text, str.c_str());
  28. }
  29.  
  30. string kmpscan(char* pat,char* text, int *f){
  31. int i,k;
  32. int len=strlen(pat);
  33. stack<int> s;
  34. stack<char> out;
  35. //s.push(0);
  36. //out.push(text[0]);
  37. for(i=k=0; text[i];){
  38. if(k==-1){
  39. s.push(k);
  40. out.push(text[i]);
  41. i++; k=0;
  42. }
  43. else if(text[i]==pat[k]){
  44. s.push(k);
  45. out.push(text[i]);
  46. i++; k++;
  47. if(k>=len){
  48. for(int c=0; c<len; c++){
  49. s.pop();
  50. out.pop();
  51. }
  52. if(!s.empty()){
  53. k=s.top();
  54. k++;
  55. }
  56. else k=0;
  57. }
  58. }else k=f[k];
  59. }
  60. string str="";
  61. stack<char> out2;
  62. while(!out.empty()){
  63. out2.push(out.top());
  64. out.pop();
  65. }
  66. while(!out2.empty()){
  67. str+=out2.top();
  68. out2.pop();
  69. }
  70. return str;
  71. }
  72.  
  73.  
  74.  
  75. int main(){
  76. int n;
  77. while(cin>>n>>pat){
  78. cin.get();
  79. kmpsetup(pat,f);
  80. for(;n>0;n--){
  81. gtln();
  82. cout<<kmpscan(pat,text,f)<<endl;
  83. }
  84. }
  85. return 0;
  86. }
  87.  

Diff to submission s1263

bugs.cpp

--- 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];
         }