Cod sursa(job #682749)

Utilizator balakraz94abcd efgh balakraz94 Data 19 februarie 2012 14:29:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<cstdio>
#include<cstring>
#include<vector>
#define infile "strmatch.in"
#define outfile "strmatch.out"
#define n_max 2000005
#define Base 73
#define MOD1 100007
#define MOD2 100021
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);
}


void Rabin_Karp ()
{
	int N = strlen(T);
	int M = strlen(P);
	
	int HP1, HP2, HT1, HT2;
	int P1, P2;
	
	HP1 = HP2 = HT1 = HT2 = 0;
    P1 = P2 = 1;	
	
	for (int i=0; i<M; ++i)
	{
		HP1 = (HP1 * Base + P[i]) % MOD1;
		HP2 = (HP2 * Base + P[i]) % MOD2;
		
		HT1 = (HT1 * Base + T[i]) % MOD1;
		HT2 = (HT2 * Base + T[i]) % MOD2;
		
		if(i)
		{
			P1 = (P1 * Base) % MOD1;
			P2 = (P2 * Base) % MOD2;
		}
	}
	
	
	for (int i=0; i <= N-M; ++i)
	{
		if(HT1 == HP1 && HT2 == HP2)
			deplasament.push_back(i);
		
		HT1 = (Base * (HT1 - (T[i] * P1) % MOD1) + T[i+M]) % MOD1;
		HT2 = (Base * (HT2 - (T[i] * P2) % MOD2) + T[i+M]) % MOD2;
	}
}


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;
}