Cod sursa(job #1902787)

Utilizator GreeDGlavan George Florian GreeD Data 4 martie 2017 19:49:03
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <string.h>

#define MAX 2000000

int suf[MAX];
int poz[1001];
int curr;


void gaseste_suf(char* s, int ls){
	int j = 0;
	int i;
	for(i = 1; i < ls;){
		if(s[j] == s[i]){
			suf[i] = j+1;
			i++;
			j++;

		}else if(j!=0){
			j = suf[j-1];
		}else{
			suf[i] = 0;
			i++;
		}
	}

}

void KMP(char* s1, int ls1, char* s2, int ls2){
	gaseste_suf(s1,ls1);
	int i = 0;
	int j = 0;
	while(i < ls1 && j < ls2){
		if(s1[i] == s2[j]){
			i++;
			j++;
		}else{
			if(i!=0){
				i = suf[i-1];
			}else{
				j++;
			}
		}
		if(i == ls1){
			if(curr <= 1000)
				poz[curr++] = j - ls1;
			i = suf[i-1];
		}
	}
}

int main(){

	FILE* f,*g;

	f = fopen("strmatch.in","r");
	g = fopen("strmatch.out","w");

	int n,m;
	char s1[MAX],s2[MAX];
	fscanf(f,"%s",s1);
	fscanf(f,"%s",s2);




	n = strlen(s1);
	m = strlen(s2);

	KMP(s1,n,s2,m);

	fprintf(g,"%d\n",curr);

	int i = 0;

	for(;i < curr; i++){
		fprintf(g,"%d ",poz[i]);
	}

}