Cod sursa(job #1116853)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 22 februarie 2014 21:02:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;

char crt;
char a[2000001], b[2000001];
long urmator[2000001], c[1024];
long i,j,M,N,nr;

void initurm() 
{ 
	long i, j;
	urmator[0] = -1; 
	for(i = 0, j = -1; i < N; i++, j++, urmator[i] = j) 
		while(j >= 0 && a[i] != a[j])
			j = urmator[j]; 
} 

void kmp() 
{ 
	long i,j;
	for (i=0, j=0; i<M; i++,j++)
	{
		while (j>=0 and a[j]!=b[i])
			j=urmator[j];
		if (j==N-1) 
			c[nr++]=i-N+1;
	}
}

int main ()
{
	FILE *f, *g;
	f=fopen("strmatch.in", "r");
    g=fopen("strmatch.out", "w");
 
    fgets(a, 2000001, f);
    fgets(b, 2000001, f);
    for (; a[N]!='\n'; ++N);
    for (; b[M]!='\n'; ++M);

	//URMATOR
	urmator[0] = -1; 
	for(i = 0, j = -1; i < N; ++i, ++j, urmator[i] = j) 
		while(j > -1 && a[i] != a[j])
			j = urmator[j]; 
		
	//KMP	
	for (i=0, j=0; i<M; ++i,++j)
	{
		while (j >- 1 and a[j]!=b[i])
			j=urmator[j];
		if (j==N-1) 
		{
			c[nr++]=i-N+1;
			j=urmator[j];
		}
	}
	
	fprintf(g, "%d\n", nr);
	if (nr>1000) nr=1000;
	for (i=0; i<nr; i++) fprintf(g, "%d ", c[i]);
	fclose(f); fclose(g);
	return 0;
}