Cod sursa(job #531197)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 9 februarie 2011 09:34:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
// infoarena: problema/strmatch //
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int MOD = 666013;
const int MOD2 = 100007;
const int MAXN = 3000010;
const int B = 257;

char c,a[MAXN],b[MAXN];
int n,m,hb,h,i,x,x2,hb2,h2;

int sol[MAXN];

int verifica(int i)
{
	int k;
	for(k=0; k<m; k++)
		if(a[k+i] != b[k])
			return 0;
	return sol[++sol[0]] = i;
}

int main()
{
	in>>b;
	m = strlen(b);	
	in>>a;
	n = strlen(a);
	
	x=x2=1;
	for(i=1; i<m; i++)
		x = (x*B)%MOD,
		x2 = (x2*B)%MOD2;
	
	for(i=0; i<m; i++)
	{
		hb = (B*hb + b[i])%MOD;
		hb2 = (B*hb2 + b[i])%MOD2;
		h = (B*h + a[i])%MOD;
		h2 = (B*h2 + a[i])%MOD2;
	}
	if(hb == h && hb2 == h2)
		sol[++sol[0]] = 0;
	
	for(i=1; i<=n-m+1; i++)
	{
		h = (((h - (x*a[i-1])%MOD + MOD)*B) + a[i+m-1])%MOD;
		h2 = (((h2 - (x2*a[i-1])%MOD2 + MOD2)*B) + a[i+m-1])%MOD2;
		if(h == hb && h2 == hb2)
			sol[++sol[0]] = i;
	}

	out<<sol[0]<<'\n';
	for(i=1, x=min(sol[0], 1000); i<=x; i++)
		out<<sol[i]<<' ';
	return 0;
}