Pagini recente » Cod sursa (job #939771) | Cod sursa (job #345406) | Cod sursa (job #2751426) | Cod sursa (job #1836264) | Cod sursa (job #2792929)
#include <fstream>
#include <stdio.h>
#include <string>
#include <queue>
using std::string;
using std::queue;
int no;
void Z_algorithm( const string& str, int* Z, const int& size, queue<int>& rez ) {
int n = str.size();
int left, right;
Z[ 0 ] = n;
left = right = 0;
for( int i = 1; i < n; i++ ) { // upss :)
if( i > right ) {
left = right = i;
while( right < n && str[ right - left ] == str[ right ] )
++right;
Z[ i ] = right - left;
right--;
} else {
int k = i - left;
if( Z[ k ] < right - i + 1 )
Z[ i ] = Z[ k ];
else {
left = i;
while( right < n && str[ right - left ] == str[ right ] )
++right;
Z[ i ] = right - left;
--right;
}
}
if( Z[ i ] == size )
if( rez.size() < 1000 )
rez.push( i - size - 1 );
else ++no;
}
}
void cauta( string text, string pattern, FILE* fout ) {
string concat = pattern + "#" + text;
int n = pattern.size();
int N = concat.size();
int* Z;
queue<int> rez;
Z = new int [ N ];
Z_algorithm( concat, Z, n, rez );
n = rez.size();
fprintf( fout, "%d\n", n + no );
for( ; !rez.empty(); rez.pop() ) // nu am putut sa ma abtin :)
fprintf( fout, "%d ", rez.front() );
}
int main()
{
string pattern, text;
std::ifstream cin( "strmatch.in" );
cin >> pattern >> text;
cin.close();
FILE *fout = fopen( "strmatch.out", "w" );
cauta( text, pattern, fout );
fclose( fout );
return 0;
}