Cod sursa(job #3295460)

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