Cod sursa(job #2035187)

Utilizator tudormaximTudor Maxim tudormaxim Data 9 octombrie 2017 00:55:45
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.06 kb
// KMP.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <string.h>
#define maxn 2000005

int Pi[maxn], Ans[maxn], size, m, n;
char Pattern[maxn], String[maxn];

void Prefix() {
	int x = 0, i;
	for (i = 2; i <= m; i++) {
		if (x > 0 && Pattern[x + 1] != Pattern[i]) x = Pi[x];
		if (Pattern[x + 1] == Pattern[i]) x++;
		Pi[i] = x;
	}
}

void KMP() {
	Prefix();
	int i, x = 0;
	for (i = 1; i <= n; i++) {
		while (x > 0 && Pattern[x + 1] != String[i]) x = Pi[x];
		if (Pattern[x + 1] == String[i]) x++;
		if (x == m) {
			Ans[size++] = i - m;
			x = Pi[x];
		}
	}
}

int main() {
	FILE *fin = fopen("strmatch.in", "r");
	FILE *fout = fopen("strmatch.out", "w");
	int i;
	fscanf(fin, "%s", (Pattern + 1));
	fscanf(fin, "%s", (String + 1));
	m = strlen(Pattern + 1);
	n = strlen(String + 1);
	KMP();
	fprintf(fout, "%d\n", size);
	size = size > 1000 ? 1000 : size;
	for (i = 0; i < size; i++) {
		fprintf(fout, "%d ", Ans[i]);
	}
	fprintf(fout, "\n");
	fclose(fin);
	fclose(fout);
    return 0;
}