Cod sursa(job #2792929)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 2 noiembrie 2021 15:26:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#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;
}