Cod sursa(job #625153)

Utilizator darkseekerBoaca Cosmin darkseeker Data 23 octombrie 2011 20:33:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <cstring>
#define MAX 2000005
using namespace std;

int n, m;
int p[MAX];            // sirul prefixelor (p[i] = j in prefixul de lung i, j este lungimeA celui mai mare prefix si totodata si sufix)
int d = -1;            // p[1..m]
char T[MAX], P[MAX];   // sirul T[0..n-1] in care se cauta si pattern-ul P[0..m-1]
int sol[1001];


void Citeste();
void Afiseaza();
void Prefix();
void KMP();

FILE *fi, *fo = fopen("strmatch.out","w");

int main()
{
	Citeste();
	KMP();
	//Afiseaza();
	return 0;
}

void Prefix()
{
	int i, k;
	p[1] = 0; k = 0;
	for (i = 1; i < m; i++)
	{
		while ( k > 0 && P[k] != P[i] )
			k =  p[k];

		if ( P[k] == P[i] ) k++;

		p[i+1] = k;
	}
}
void DEBUG()
{
	for ( int i = 1; i <= m; i++ )
		fprintf(fo, "%d ", p[i]);
	fprintf(fo, "\n");
}

void KMP()
{
	Prefix();
	//DEBUG();
	int i, j = 0,solCount = 0;
	for (i = 0; i < n; i++)
	{
		while ( j > 0 && P[j] != T[i] )       // j > 0 nu exista poz 0 in p[]
			j = p[j];
		if ( P[j] == T[i] ) j++;

		if ( j == m )
 		{
			if(solCount < 1000)
				sol[++solCount] = i - m + 1;
		}
	}
	
	fprintf(fo,"%d\n",solCount);
	for(i=1; i<=solCount; i++)
		fprintf(fo,"%d ",sol[i]);
	fprintf(fo,"%c",'\n');
}


void Citeste()
{
	fi = fopen("strmatch.in","r");
	fscanf(fi," %s", P);
	fscanf(fi, "%s", T);
	n = strlen(T);
	m = strlen(P);
	fclose(fi);
}
 
void Afiseaza()
{
	fprintf(fo, "%d", d);
	fclose(fo);
}