Cod sursa(job #415817)

Utilizator slayer4uVictor Popescu slayer4u Data 11 martie 2010 21:11:21
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string a, b;
vector <int> rez;

long p = 991, win = 1559, alen, blen, b_hash, a_hash, rez_size, def_power, power;

int main ()
{
	freopen ("strmatch.in", "rt", stdin);
	freopen ("strmatch.out", "wt", stdout);

	cin.sync_with_stdio(false);
	cin>>a;
	cin>>b;

	a_hash = 0;
	b_hash = 0;
	alen = a.size();
	blen = b.size();
	power = 1;
	for (long i = alen - 1; i >= 0; --i)
	{
		a_hash += a[i] * power;
		b_hash += b[i] * power;
		def_power = power;
		power *= p;
		a_hash %= win;
		b_hash %= win;
		power %= win;
	}

	for (long i = alen; i < blen; ++i)
	{
		if (a_hash == b_hash)
		{
			rez.push_back(i);
		}

		b_hash += (win - (def_power * b[i - alen] % win));
		b_hash %= win;
		if (b_hash < 0) 
			b_hash += win;
		b_hash *= p;
		b_hash += b[i];
		b_hash %= win;
	}

	printf("%ld\n", rez.size());
	rez_size = rez.size();
	for (long i = 0; i < rez_size && i < 1000; ++i)
		printf("%ld ", rez[i] - alen);
	printf("\n");
	return 0;
}