Cod sursa(job #103115)

Utilizator c_sebiSebastian Crisan c_sebi Data 14 noiembrie 2007 22:09:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 0.66 kb
#include <stdio.h>
#include <string.h>
#define MAX 10010

int n, m, nr, Urm[MAX];
char t[MAX], p[21];

void urm(){
	int k=-1, x;
	Urm[0]=0;
	for(x=1; x<m; ++x){
		while (k>0 && p[k+1]!=p[x]) k  = Urm[k];
		if(p[k+1]==p[x]) k++;
		Urm[x]=k;
		}
}

void kmp(){
	int i, x=-1;
	n=strlen(t), m=strlen(p);
	urm();
	for(i=0; i<n; ++i){
		while(x>0 && p[x+1]!=t[i]) x=Urm[x];
		if(p[x+1]==t[i]) x++;
		if(x==m-1) {x=Urm[x]; nr++;}
	}
}

int main(){
	FILE *f=fopen("abc2.in" , "r");
	FILE *g=fopen("abc2.out" , "w");
	fscanf(f, "%s\n", &t);
	while(fscanf(f, "%s\n", &p)!=EOF)
		kmp();
	fprintf(g, "%d\n", nr-1);
	fclose(f);
	fclose(g);
	return 0;
}