Cod sursa(job #2014762)

Utilizator mihai.alphamihai craciun mihai.alpha Data 24 august 2017 13:02:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <algorithm>
#include <string.h>

FILE *fin, *fout;

#define MAXDIM 2000000

int N, M;
char n[MAXDIM + 2], m[MAXDIM + 2];
int pi[MAXDIM + 1];
int ans[MAXDIM + 1];

int main() {
	fin = fopen("strmatch.in", "r");
	fout = fopen("strmatch.out", "w");
	fgets(n + 1, MAXDIM + 3, fin);
	fgets(m + 1, MAXDIM + 3, fin);
	N = strlen(n + 1) - 1;
	M = strlen(m + 1) - 1;///gaseste toate ap lui n in m
	pi[1] = 0;
	int k = 0;
	for (int i = 2; i <= N; i++) {
		while (k > 0 && n[i] != n[k + 1])
			k = pi[k];
		if (n[i] == n[k + 1])
			k++;
		pi[i] = k;
	}
	k = 0;
	for (int i = 1; i <= M; i++) {
		while (k > 0 && m[i] != n[k + 1])
			k = pi[k];
		if (m[i] == n[k + 1]) {
			k++;
		}
		if (k == N) {
			if (ans[0] < 1000)
				ans[++ans[0]] = i - N;
			else
				++ans[0];
		}
	}
	fprintf(fout, "%d\n", ans[0]);
	for (int i = 1; i <= std::min(1000, ans[0]); i++)
		fprintf(fout, "%d ", ans[i]);
	fclose(fin);
	fclose(fout);
	return 0;
}