Source code for submission s869

Go to diff to previous submission

bugs.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. int myFind ( int lastPos, int length, string & line, string & text, bool *& erased, bool & count )
  9.  {
  10.    int k = 0;
  11.    bool toErase = true; 
  12.    for ( int i = lastPos; i < (int)(length - text.length()); i++ )
  13.     {
  14.       if ( erased[i] == false && line[i] == text[0] )
  15.        {
  16.          k = 1;
  17.          for ( int j = i + 1; j < (int)(i + text.length()); j++ )
  18.           {
  19.             while ( erased[j] )
  20.               j++;
  21.             if ( j >= length || line[j] != text[k++] )
  22.              {
  23.                toErase = false;
  24.                break;
  25.              }
  26.           }
  27.          if ( toErase )
  28.           {
  29.             k = i;
  30.             for ( int z = i; z < i + (int)text.length(); z++ )
  31.              {
  32.                while ( erased[k] )
  33.                  k++;
  34.                erased[k] = true;
  35.              }  
  36.             count = true;  
  37.             return i; 
  38.           } 
  39.          toErase = true; 
  40.        }   
  41.     }
  42.    return -1; 
  43.  }
  44.  
  45. void analyseLine ( string & text, string & line, bool * erased )
  46.  {
  47.    int length = (int) line.length();
  48.    int lastPos = 0;
  49.    bool count = false;
  50.    if ( !length ) 
  51.     {
  52.       cout << endl;
  53.       return;
  54.     }   
  55.    while ( 1 )
  56.     {
  57.       lastPos = myFind ( lastPos, length, line, text, erased, count );
  58.       if ( lastPos == -1 )
  59.         break;
  60.       lastPos = (int)lastPos - text.length() + 1 >= 0 ? lastPos - (int)text.length() + 1 : 0;
  61.     } 
  62.    if ( !count ) 
  63.      cout << line << endl;
  64.    else
  65.     {
  66.       for ( int i = 0; i < length; i++ )
  67.        {
  68.          if ( !erased[i] )
  69.            cout << line[i];
  70.        }
  71.       cout << endl; 
  72.     } 
  73.  }
  74.  
  75. int main ( void )
  76.  {
  77.    int n, i, j;
  78.    char bug[1010];
  79.    char tmp;
  80.    bool erased[2000010];
  81.    string text, line;
  82.  
  83.    while ( scanf ( "%d %s%c", &n, bug, &tmp ) == 3 )
  84.     {
  85.       text = string ( bug );
  86.       for ( i = 0; i < n; i++ )
  87.        {
  88.          getline ( cin, line );
  89.          for ( j = 0; j < (int)line.length(); j++ )
  90.            erased[j] = false;
  91.          analyseLine ( text, line, erased );
  92.        } 
  93.     }
  94.    return 0;
  95.  }
  96.  

Diff to submission s753

bugs.cpp

--- c4.s753.cteam019.bugs.cpp.0.bugs.cpp
+++ c4.s869.cteam019.bugs.cpp.0.bugs.cpp
@@ -6,35 +6,78 @@
 using namespace std;
 
-void analyseLine ( string & text, string & line )
+int myFind ( int lastPos, int length, string & line, string & text, bool *& erased, bool & count )
  {
-   string::size_type lastPos = 0;
-   if ( !line.length() )
+   int k = 0;
+   bool toErase = true; 
+   for ( int i = lastPos; i < (int)(length - text.length()); i++ )
+    {
+      if ( erased[i] == false && line[i] == text[0] )
+       {
+         k = 1;
+         for ( int j = i + 1; j < (int)(i + text.length()); j++ )
+          {
+            while ( erased[j] )
+              j++;
+            if ( j >= length || line[j] != text[k++] )
+             {
+               toErase = false;
+               break;
+             }
+          }
+         if ( toErase )
+          {
+            k = i;
+            for ( int z = i; z < i + (int)text.length(); z++ )
+             {
+               while ( erased[k] )
+                 k++;
+               erased[k] = true;
+             }  
+            count = true;  
+            return i; 
+          } 
+         toErase = true; 
+       }   
+    }
+   return -1; 
+ }
+
+void analyseLine ( string & text, string & line, bool * erased )
+ {
+   int length = (int) line.length();
+   int lastPos = 0;
+   bool count = false;
+   if ( !length ) 
     {
       cout << endl;
       return;
-    }
+    }   
    while ( 1 )
     {
-      lastPos = line.find ( text, lastPos );
-      if ( lastPos == string::npos )
+      lastPos = myFind ( lastPos, length, line, text, erased, count );
+      if ( lastPos == -1 )
+        break;
+      lastPos = (int)lastPos - text.length() + 1 >= 0 ? lastPos - (int)text.length() + 1 : 0;
+    } 
+   if ( !count ) 
+     cout << line << endl;
+   else
+    {
+      for ( int i = 0; i < length; i++ )
        {
-         //cout << lastPos << " " << string::npos << endl;
-         break;
-       }  
-      line = line.erase ( lastPos, text.length() );
-      //cout << "PO ERASU:" << line << " pos:" << lastPos << endl;
-      lastPos = ( lastPos - text.length() + 1 < 0 ) || ( lastPos - text.length() + 1 > 2500000 ) ? 0 : lastPos - text.length() + 1;
-      //cout << lastPos << endl;
-    }   
-   cout << line << endl; 
+         if ( !erased[i] )
+           cout << line[i];
+       }
+      cout << endl; 
+    } 
  }
 
 int main ( void )
  {
-   int n, i;
+   int n, i, j;
    char bug[1010];
    char tmp;
-   string line;
-   string text;
+   bool erased[2000010];
+   string text, line;
    
    while ( scanf ( "%d %s%c", &n, bug, &tmp ) == 3 )
@@ -44,5 +87,7 @@
        {
          getline ( cin, line );
-         analyseLine ( text, line );
+         for ( j = 0; j < (int)line.length(); j++ )
+           erased[j] = false;
+         analyseLine ( text, line, erased );
        } 
     }