Cod sursa(job #2792928)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 2 noiembrie 2021 15:06:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <stdio.h>
#include <string>
#include <queue>

using std::string;
using std::queue;

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++ ) {
		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 )
			rez.push( i - size - 1 );

	}
}

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