Cod sursa(job #1437124)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 16 mai 2015 22:43:21
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 2000005

int* prefix(char A[]);
void kmp(char B[], char A[], int v[], int* nr);

int main(){
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	char A[MAX], B[MAX];
	int v[1005], nr = -1, i;
	scanf("%s\n%s", A, B);
	kmp(B, A, v, &nr);
	printf("%d\n", nr + 1);
	for(i = 0; i <= nr; i++)
		printf("%d ", v[i]);
	printf("\n");
	return 0;
}

int* prefix(char A[]){
	int n = strlen(A), k, q;
	int* pr = malloc(n * sizeof(int));
	if(!pr) return NULL;
	pr[0] = 0;
	k = 0;
	for(q = 1; q < n; q++){
		while(k > 0 && A[k] != A[q])
			k = pr[k];
		if(A[k] == A[q])
			k++;
		pr[q] = k;
	}
	
	return pr;
}

void kmp(char B[], char A[], int v[], int* nr){
	int n = strlen(B);
	int m = strlen(A);
	int* pr = prefix(A), q = 0, i;
	for(i = 0; i < n; i++){
		while(q > 0 && A[q] != B[i])
			q = pr[q - 1];
		if(A[q] == B[i])
			q++;
		if(q == m){
			(*nr)++;
			v[*nr] = i - m + 1;
			if(*nr == 999)
				return;
			q = pr[q - 1];
		}
	}
}