Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <string> #include <iostream> using namespace std; int myFind ( int lastPos, int length, string & line, string & text, bool *& erased, bool & count ) { 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 = 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++ ) { if ( !erased[i] ) cout << line[i]; } cout << endl; } } int main ( void ) { int n, i, j; char bug[1010]; char tmp; bool erased[2000010]; string text, line; while ( scanf ( "%d %s%c", &n, bug, &tmp ) == 3 ) { text = string ( bug ); for ( i = 0; i < n; i++ ) { getline ( cin, line ); for ( j = 0; j < (int)line.length(); j++ ) erased[j] = false; analyseLine ( text, line, erased ); } } return 0; }
--- 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 ); } }