Cod sursa(job #761056)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 24 iunie 2012 16:15:09
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<stdio.h>
#include<string.h>
#define LMAX 2000005
char A[ LMAX ], B[ LMAX ];
int len1, len2, L[ LMAX ], v [ 1005 ], nr;
void read()
{
	int i;
	FILE *f = fopen("strmatch.in", "r");
	fgets(A, 2000003, f);
	len1 = strlen(A) - 2;
	fgets(B, 2000003, f);
	len2 = strlen(B) - 2;
	fclose(f);
}
void Prefix()
{
	int i, k;
	for(i = 1; i <= len1; i++)
	{
		k = L[i-1];
		while(k > 0 && A[k+1] != A[i])
			k = L[k];
		if(A[k+1] == A[i])
			k++;
		L[i] = k;
	}
}
void KMP()
{
	int i, k;
	k = 0;
	for(i = 0; i <= len2; i++)
	{
		while(k > 0 && A[k+1] != B[i])
			k = L[k];
		if(A[k+1] == B[i])
			k++;
		if(k == len1)
		{
			nr++;
			if(nr <= 1000)
				 v[nr] = i - len1; 
			k = L[k];
		}
	}
}
void write()
{
	int q;
	FILE *g = fopen("strmatch.out", "w");
	fprintf(g, "%d\n", nr);
	if(nr > 1000)
		nr = 1000;
	for(q = 1; q <= nr; q++)
		fprintf(g, "%d ", v[q]);
	fprintf(g, "\n");
	fclose(g);
}
int main()
{
	read();
	Prefix();
	KMP();
	write();
	return 0;
}