Cod sursa(job #1690668)

Utilizator andreilucaLuca Andrei andreiluca Data 15 aprilie 2016 14:40:23
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#define NMAX 2000000
using namespace std;
FILE * in, *out;
char s[NMAX],pattern[NMAX];
int n, np;
int power;
int base = 74;
int h(char * s, int start, int length);
int update(int x, int i, char * sir);
int code_pattern;
void read();
void solve();
int main()
{
	in = fopen("strmatch.in", "r");
	out = fopen("strmatch.out", "w");
	read();
	code_pattern = h(pattern,0,np);
	//printf("%d", code_pattern);
	power = pow((double)base,(double)np);
	solve();

	return 0;
}

void read()
{
	fscanf(in,"%s",&pattern);
	fscanf(in, "%s", &s);
	n = strlen(s);
	np = strlen(pattern);
	//printf("%s\n%s", pattern, s);
}
int h(char * s, int start, int length)
{
	int code = 0;
	int p = 1;
	for (int i = start + length - 1; i >= start; i--)
	{
		code += (s[i] - '0') * p;
		p = p*base;
	}
	return code;
}
int update(int x, int i, char * sir)
{
	int y;
	int aux;
	y = x*base - (sir[i - 1]- '0') * power + (sir[i + np - 1]-'0');
	return y;
}
void solve()
{
	queue<int> q;
	int hsubsir = h(s, 0, np);
	for (int i = 1; i <= n - np+1; i++)
	{
		if (hsubsir == code_pattern)
			q.push(i-1);
		hsubsir = update(hsubsir, i, s);
	}
	fprintf(out, "%d\n", q.size());
	int dim = q.size();
	for (int i = 0; i <dim ; i++)
	{
		fprintf(out, "%d ", q.front());
		q.pop();
	}
}