Cod sursa(job #847864)

Utilizator OpportunityVlad Negura Opportunity Data 4 ianuarie 2013 16:29:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <string>

using namespace std;

ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

string a,b;
long long h,k,n,m,i,v[1001],vn;
const long long mod=104729;


int main(){
	
	fi >> a >> b; n = a.size(); m = b.size();
	if (n>m) { fo << "0\n"; return 0; }
	
	for (i=0; i<n; i++){
		k += a[i] % mod;
		h += b[i] % mod;
	}
	
	if ((k==h)&&(b.substr(0,n)==a)) vn++;
	
	for (i=n; i<m && vn<1000; i++){
		h = (h-b[i-n]+b[i])%mod;
		if ((k==h)&&(b.substr(i-n+1,n)==a)) v[vn++] = i-n+1;
	}
	
	fo << vn << "\n";
	for (i=0; i<vn; i++) fo << v[i] << " ";
	
	return 0;
}