Cod sursa(job #1990549)

Utilizator KeitaroAbderus Alastor Keitaro Data 12 iunie 2017 15:19:30
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<math.h>
#include<string.h>.

using namespace std;
#define nMax 10000
#define prime 101

int hashf(char *p, int start, int end) { //hashing function
	long hash_value = 0;
	long p_up = 0;
	for (int i = start; i < end; i++)
	{
		hash_value += p[i] * pow(prime, p_up);
		p_up++;
	}
	return hash_value;
}

bool compare(char *str2, int start, int end, char *str1) {
	int q = 0;
	bool flag = true;
	for (int i = start; i < end; i++) {
		if (str2[i] == str1[q]) {
			q++;
		}
		else {
			flag = false;
		}
	}
	return flag;
}

void RabinKarp(char *str1, char *str2) {
	int count = 0; //number of times
	int show_array[nMax]; //positions where it appears
	int nl = strlen(str1);
	int mu = strlen(str2);
	int h_str1 = hashf(str1,0,nl);

	for (int i = 0; i <= mu - nl; i++) {
		long h_str2 = hashf(str2, i, i + nl);
		if (h_str1 == h_str2) {
			if (true == compare(str2, i, i + nl, str1)) { //actual checking if strings are the same
				show_array[count] = i;
				count++;
			}
		}
	}
	printf("%d\n", count);
	for (int i = 0; i < count; i++) {
		printf("%d ", show_array[i]);
	}
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	char str1[nMax], str2[nMax];
	char *p1, *p2;
	scanf("%s %s", str1, str2);
	RabinKarp(str1, str2);
	return 0;
}