Cod sursa(job #2066848)

Utilizator calin1Serban Calin calin1 Data 15 noiembrie 2017 16:34:37
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define mod 101
#define N 2000005

using namespace std;

char sir_init[N], sir[N], puteri_123[N], puteri_24[N];

int init_hash_1, init_hash_2, tmp_hash_1, tmp_hash_2, l_sir_init;

vector <int> vec;

void creare_puteri(int baza, char vec[])
{
	vec[0] = 1;
	
	for(int i = 1 ; i < l_sir_init ; ++i)
	{
		vec[i] = (vec[i - 1] * baza) % mod;
	}
}

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

int comparare(int start)
{
	if(init_hash_1 == tmp_hash_1)
	{
		if(init_hash_2 == tmp_hash_2)
		{
			if!(strncmp(sir_init, sir + start, l_sir_init))
			{
				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);
	
	creare_puteri(123,puteri_123);
	creare_puteri(24,puteri_24);
	
	create_hash(puteri_123, init_hash_1, sir_init, l_sir_init);
	create_hash(puteri_24, init_hash_2, sir_init, l_sir_init);
	
	create_hash(puteri_123, tmp_hash_1, sir, l_sir_init);
	create_hash(puteri_24, tmp_hash_2, sir, l_sir_init);
	
	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] * puteri_123[l_sir_init - 1]) % mod)) * 123) % mod + sir[i + l_sir_init - 1]) % mod;
		tmp_hash_2 = (((tmp_hash_2 - ((sir[i - 1] * puteri_24[l_sir_init - 1]) % 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();
	
	printf("\n");
}

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