Cod sursa(job #1437133)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 16 mai 2015 23:13:27
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.14 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 = 0, i;
	scanf("%s\n%s", A, B);
	for(i = strlen(A); i > 0; i--)
		A[i] = A[i - 1];
	for(i = strlen(B); i > 0; i--)
		B[i] = B[i - 1];
	A[0] = ' ';
	B[0] = ' ';
	kmp(B, A, v, &nr);
	printf("%d\n", nr);
	for(i = 1; i <= nr && i <= 1000; i++)
		printf("%d ", v[i]);
	printf("\n");
	return 0;
}

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

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