Cod sursa(job #332740)

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

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;
	int hp=0, h=0;
	
	for(i = 1; i < n; ++i)
		pw255 *=255, pw255 %= mod;
	
	for(i = 1; i <= n; ++i)
		hp = hp * 255 + p[i], hp %= mod;
	
	for(i = 1; i < n; ++i)
		h = h * 255 + a[i], h %= mod;
	
	for(i = n; i <= m; ++i)
	{
		h = h * 255 + a[i], h %= mod;
		
		if(h == hp)
			if(verify(i-n+1, i)) sol.push_back(i-n);//printf("%d ", i-n+1);
		
		h -= (a[i-n+1] * pw255)%mod;
			
		while(h < 0) h += mod;
		
		
	}
	
	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;
}