Cod sursa(job #3295452)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 5 mai 2025 20:01:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <vector>
using namespace std;
vector <int> ras;
int z[4000005];
int main(){
	int i, target, best;
	string a, b;
	ifstream fin( "strmatch.in" );
	ofstream fout( "strmatch.out" );
	fin >> a >> b;
	target = a.size();
	a += '$';
	a += b;
	best = 0;
	for( i = 1; i < a.size(); i++ ){
		if( i <= best + z[best] - 1 ){
			z[i] = min( z[i - best], best + z[best] - i );
		}
		while( i + z[i] < a.size() && a[z[i]] == a[i + z[i]] ){
			z[i]++;
		}
		if( i + z[i] > best + z[best] ){
			best = i;
		}
		if( z[i] == target ){
			ras.push_back( i - target - 1 );
		}
	}
	fout << ras.size() << '\n';
	for( i = 0; i < min( ( int )ras.size(), 1000 ); i++ ){
		fout << ras[i] << ' ';
	}
	return 0;
}