Cod sursa(job #2067271)

Utilizator calin1Serban Calin calin1 Data 16 noiembrie 2017 08:57:03
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define mod 101
#define N 2000005

using namespace std;

int init_hash_1, init_hash_2, tmp_hash_1, tmp_hash_2, l_sir_init, putere_123, putere_24;

char sir_init[N], sir[N];

vector <int> vec;

void create_hash(int baza, int &x, char vec[], int &putere)
{
	putere = 1;
	
	for(int i = l_sir_init - 1 ; i >= 0 ; --i)
	{
		x += (vec[i] * putere) % mod;
		
		x %= mod;
		
		if(i > 0)
		{
			putere *= baza;
		
			putere %= mod;
		}
	}
}

int comparare(int start)
{
	if(init_hash_1 == tmp_hash_1)
	{
		if(init_hash_2 == tmp_hash_2)
		{
			for(int i = start ; i < start + l_sir_init; ++i)
			{
				if(sir_init[i - start] != sir[i])
				{
					return 0;
				}
			}
			return 1;
		}
	}
	
	return 0;
}

void afisare()
{
	printf("%d\n", vec.size());
	
	for(int i = 0 ; i < vec.size() && i < 1000; ++i)
	{
		printf("%d ", vec[i]);
	}
}

void solve()
{
	l_sir_init = strlen(sir_init);
	
	create_hash(123, init_hash_1, sir_init,putere_123);
	create_hash(24, init_hash_2, sir_init,putere_24);
	
	create_hash(123, tmp_hash_1, sir,putere_123);
	create_hash(24, tmp_hash_2, sir,putere_24);
	
	if(comparare(0))
	{
		vec.push_back(0);
	}
	
	int tmp_l = strlen(sir) - l_sir_init;
	
	for(int i = 1 ; i < tmp_l ; ++i)
	{
		tmp_hash_1 = (((tmp_hash_1 - ((sir[i - 1] * putere_123) % mod)) * 123) % mod + sir[i + l_sir_init - 1]) % mod;
		tmp_hash_2 = (((tmp_hash_2 - ((sir[i - 1] * putere_24) % mod)) * 24) % mod + sir[i + l_sir_init - 1]) % mod;
		
		if(comparare(i))
		{
			vec.push_back(i);
		}
	}
	
	afisare();
}

void citire()
{
	fgets(sir_init,N,stdin);
	fgets(sir,N,stdin);
	
	if(sir_init[strlen(sir_init) - 1] == '\n')
	{
		sir_init[strlen(sir_init) - 1] = NULL;
	}
	
	if(sir[strlen(sir) - 1] == '\n')
	{
		sir[strlen(sir) - 1] = NULL;
	}
	
	solve();
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	citire();
}