Cod sursa(job #2167911)

Utilizator tudormaximTudor Maxim tudormaxim Data 14 martie 2018 01:50:34
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.32 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 2000005

int min(int x, int y) {
    return x < y ? x : y;
}

int* KMP(char* String, char* Pattern, int* size) {

	int m = strlen(Pattern);
	int n = strlen(String);
	int *Pi = (int*)malloc(sizeof(int) * MAXN);
	int* ans = (int*) malloc(sizeof(int) * MAXN);
    memset(ans, 0, sizeof(ans));

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

	x = 0;
	for (i = 0; i < n; i++) {
		while (x > 0 && Pattern[x] != String[i])
            x = Pi[x - 1];
		if (Pattern[x] == String[i])
            x++;
		if (x == m) {
			ans[(*size)++] = i - x + 1;
		}
	}
	return ans;
}

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

    char* String = (char*)malloc(sizeof(char) * MAXN);
    char* Pattern = (char*) malloc(sizeof(char) * MAXN);
    int size = 0, i;

    scanf("%s", Pattern);
    scanf("%s", String);

    int* ans = KMP(String, Pattern, &size);

    printf("%d \n", size);
    for (i = 0; i < min(size, 1000); i++) {
        printf("%d ", ans[i]);
    }

    printf("\n");
    free(String);
    free(Pattern);
    free(ans);
    return 0;
}