Cod sursa(job #682693)

Utilizator balakraz94abcd efgh balakraz94 Data 19 februarie 2012 13:25:09
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<cstdio>
#include<cstring>
#include<vector>
#include<ctype.h>
#define infile "strmatch.in"
#define outfile "strmatch.out"
#define n_max 2000005
#define MOD 666013
#define d 62
using namespace std;


char P[n_max], T[n_max];

vector < int > deplasament;


void citeste()
{
	freopen(infile, "r", stdin);
	
	gets(P);
	gets(T);
	
	fclose(stdin);
}


inline int numb(char c)
{
	if(isdigit(c))
		return c - '0';
	
    if(isupper(c))
		return c - 55;
	
	return c - 61;
}


inline int powlog(int x, int p)
{
	if (p == 0)
		return 1;
	
	int sqr = powlog(x, p/2) % MOD;
	
	sqr = (sqr * sqr) % MOD;
	
	if (p & 1) 
		sqr = 1LL* x * sqr % MOD;
	
	return sqr;
}


void Rabin_Karp ()
{
	int N = strlen(T);
	int M = strlen(P);
	
	int h = powlog(d, M-1);
	
	int p = 0, t = 0;
	
	for (int i=0; i<M; ++i)
	{
		p = (d*p + numb(P[i])) % MOD;
		t = (d*t + numb(T[i])) % MOD;
	}
	
	for (int i=0; i <= N-M; ++i)
		if (p == t)
		{
			bool gasit = 1;
			
			for (int j=0; j<M && gasit; j++)
				if (P[j] != T[i+j])
					gasit = 0; 
				
			if (gasit) 
				deplasament.push_back(i);
		} 
		else 
			t = (d*(t - ((numb(T[i])*h) % MOD)) + numb(T[i+M])) % MOD;
}


void afiseaza()
{
	freopen(outfile, "w", stdout);
	
	printf("%d\n", deplasament.size());
	
	for(unsigned int i = 0; i < deplasament.size() && i < 1000; ++i)
		printf("%d ",deplasament[i]);
	printf("\n");
	
	fclose(stdout);
}


int main()
{
	citeste();
	
	Rabin_Karp();
	
	afiseaza();
	
	return 0;
}