Cod sursa(job #1116802)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 22 februarie 2014 20:24:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

char crt;
char a[2000001], b[2000001];
long urmator[2000001], c[2000001];
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");
	fscanf(f, "%c", &crt);
	while (crt!='\n')
	{
		a[N++]=crt;
		fscanf(f, "%c", &crt);
	}
	fscanf(f, "%c", &crt);
	while (crt!='\n')
	{
		b[M++]=crt;
		fscanf(f, "%c", &crt);
	}
	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]; 
		
		
	
 
 for(i = 0, j = 0; i < M; i++, j++) 
 {
    while(j >= 0 && b[i] != a[j]) 
       j = urmator[j]; 
	if (j==N-1) 
			c[nr++]=i-N+1;
}


	fprintf(g, "%d\n", nr);
	for (i=0; i<nr && i<1000; i++) fprintf(g, "%d ", c[i]);
	fclose(f); fclose(g);
	return 0;
}