Cod sursa(job #531187)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 9 februarie 2011 09:01:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 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 MAXN = 2000010;
const int B = 257;

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

vector<int> sol;

void verifica(int i)
{
	int k;
	for(k=1; k<=m; k++)
		if(a[k+i-1] != b[k])
			return;
	sol.push_back(i);
}

int main()
{
	in>>s;
	m = strlen(s);
	for(i=1; i<=m; i++)
		b[i] = s[i-1];
	in>>s;
	n = strlen(s);
	for(i=1; i<=n; i++)
		a[i] = s[i-1];
	
	h = hb = 0;
	
	x=1;
	for(i=1; i<m; i++)
		x = (x*B)%MOD;
	
	for(i=1; i<=m; i++)
	{
		hb = (B*hb + b[i])%MOD;
		h = (B*h + a[i])%MOD;
	}
	if(hb == h)
		verifica(1);
	
	for(i=2; i<=n-m+1; i++)
	{
		h = (((h - (x*a[i-1])%MOD + MOD)*B)%MOD + a[i+m-1])%MOD;
		if(h == hb)
			verifica(i);
	}
	
	//out<<x<<endl;
	//out<<hb<<endl;
	//for(i=1; i<=n-m+1; i++)
	//	out<<h[i]<<' ';
	out<<sol.size()<<'\n';
	for(i=0; i<sol.size(); i++)
		out<<sol[i]-1<<' ';
	
	return 0;
}