Cod sursa(job #760697)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 22 iunie 2012 17:29:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#include<string.h>
#define LMAX 2000005
char A[ LMAX ], B[ LMAX ];
int len1, len2, L[ LMAX ], v [ LMAX ], nr;
void read()
{
	char c;
	FILE *f = fopen("strmatch.in", "r");
	fscanf(f, "%c", &c);
	while(c != '\n')
	{
		len1++;
		A[ len1 ] = c;
		fscanf(f, "%c", &c);
	}
	
	fscanf(f, "%c", &c);
	while(c != '\n')
	{
		len2++;
		B[ len2 ] = c;
		fscanf(f, "%c", &c);
	}
		
	fclose(f);
}
void Prefix()
{
	int i, k;
	for(i = 2; 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 = 1; 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++, v[nr] = i - len1, k = L[k];
	}
}
void write()
{
	int q;
	FILE *g = fopen("strmatch.out", "w");
	fprintf(g, "%d\n", nr);
	for(q = 1; q <= nr; q++)
		fprintf(g, "%d ", v[q]);
	fprintf(g, "\n");
	fclose(g);
}
int main()
{
	read();
	Prefix();
	KMP();
	write();
	return 0;
}