Cod sursa(job #3368930)

Utilizator reeaandreeaholtea andreea reeaandreea Data 16 octombrie 2026 16:37:53
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb

#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");


int main()
{
	string a,b;
	fin>>a>>b;

	int n=a.size();
	int m=b.size();

	if(n>m) {
		fout<<0<<"\n\n";
		return 0;
	}



	long long ha=0,hb=0,p=1;

	int mod=123456791;
	for(int i=0; i<n; i++) {
		ha=(ha*37+a[i])%mod;
		hb=(hb*37+b[i])%mod;

		if(i<n-1) {
			p=p*37%mod;
		}

	}

	int cnt=0;
	vector<int> poz;

	for(int i=0; i<=m-n; i++) {
		if(ha==hb&& b.compare(i,n,a)==0) {
			cnt++;


			if(poz.size()<1000)
				poz.push_back(i);
		}

		if(i<m-n) {
			hb=(hb-b[i]*p%mod+mod)%mod;
			hb=(hb*37+b[i+n])%mod;
		}


	}


	fout<<cnt<<'\n';

	for(int x:poz) {
		fout<<x<<' ';
	}
	return 0;
}