Cod sursa(job #629411)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 3 noiembrie 2011 12:06:27
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
#define NMAX 2000010
#define B 53
#define MOD 104729

using namespace std;

char c1[NMAX], c2[NMAX];
int n, m, st[NMAX], dr[NMAX], P=1, ha, hb, fin=0;
short  a[NMAX], b[NMAX];

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

int cif(char c)
{
	if (c>='A' && c<='Z') return c-'A';
	else return 'Z'-'A'+c-'a'+1;
}

void Preprop()
{
	int i;
	n=strlen(c1); m=strlen(c2);
	for (i=0; i<m; ++i) a[i+1]=cif(c2[i]);
	for (i=0; i<n; ++i)
	{
		b[i+1]=cif(c1[i]);
		hb=((hb*B)%MOD+b[i+1])%MOD; 
		if (i>0)P=(P*B)%MOD;
	}
	for (i=0; i<n; ++i) 
		ha=((ha*B)%MOD+a[i+1])%MOD;
}

int match(int st, int dr)
{
	int ok=1, i;
	for (i=1; i<=n; ++i)
		if (b[i]!=a[i+st-1]) {ok=0; break;}
	return ok;
}

void Solve()
{
	int i;
	if (ha==hb && match(1, n)) st[++fin]=1, dr[fin]=n;
	
	for (i=2; i<=m-n+1; ++i)
	{
		ha=(((((ha-(a[i-1]*P)%MOD)+MOD)%MOD)*B)%MOD + a[n+i-1])%MOD;
		if (ha==hb && match(i, n-i+1)) st[++fin]=i, dr[fin]=n-i+1;
	}
}

void Write()
{
	int i;
	g<<fin<<"\n";
	for (i=1; i<=min(1000, fin); ++i) g<<st[i]-1<<" ";
}

int main()
{
	f.getline(c1, NMAX);
	f.getline(c2, NMAX);
	
	Preprop();
	
	Solve();
	
	Write();
	
	f.close();
	g.close();
	return 0;
}