Cod sursa(job #332747)

Utilizator blasterzMircea Dima blasterz Data 19 iulie 2009 16:59:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
//Rabin-Karp
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define N 2000001
#define mod 2000003
#define mod2 666013

using namespace std;
char a[N], p[N];
int n, m;
vector<int> sol;

inline int verify(int x, int y)
{
	for(int i = x, j = 1; i <= y; ++i, ++j)
		if(a[i] != p[j]) return 0;
	return 1;
}

void rk()
{
	int pw255=1, i, pw2255=1;
	int hp=0, h=0;
	int hp2=0, h2=0;
	for(i = 1; i < n; ++i)
		pw255 *=255, pw255 %= mod,
		pw2255 *= 255, pw2255 %= mod2;
	
	for(i = 1; i <= n; ++i)
		hp = hp * 255 + p[i], hp %= mod,
		hp2 = hp2 * 255 + p[i], hp2 %= mod2;
	
	for(i = 1; i < n; ++i)
		h = h * 255 + a[i], h %= mod,
		h2 = h2 * 255 + a[i], h2 %= mod2;
	
	for(i = n; i <= m; ++i)
	{
		h = h * 255 + a[i], h %= mod;
		h2 = h2 * 255 + a[i], h2 %= mod2;
		
		if(h == hp)
			if(h2 == hp2) if(sol.size() < 1000) sol.push_back(i-n);//printf("%d ", i-n+1);
		
		h -= (a[i-n+1] * pw255)%mod;
		h2 -= (a[i-n+1] * pw2255) % mod2;
		
		while(h < 0) h += mod;
		while(h2 < 0) h2 += mod2;
		
	}
	
	printf("%d\n", sol.size());
	
	if(n <= 1000)
	{
		for(int i = 0; i < sol.size(); ++i) printf("%d ", sol[i]);
		printf("\n");
	}
	else
	{
		for(int i = 0; i < min(1000, (int)sol.size()); ++i) printf("%d ", sol[i]);
		printf("\n");
	}
	
	
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s\n", &p);
	scanf("%s\n", &a);
	
	n = strlen(p);
	m = strlen(a);
	
	int i;
	for(i = n; i > 0; --i) p[i] = p[i-1];
	for(i = m ; i > 0;--i) a[i] = a[i-1];
	
	rk();
	return 0;
}