Cod sursa(job #748499)

Utilizator IeewIordache Bogdan Ieew Data 13 mai 2012 17:03:10
Problema Potrivirea sirurilor Scor 18
Compilator c Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <string.h>
char a[2000001];
char b[2000001];
int n,m;
int app[1024], k;
int next[2000000];

void calc_next()
{
	int i,j = 0;
	
	for(i = 2;i < n;i++)
	{
		while( j && a[j] != a[i])
			j = next[j];
		if(a[j] == a[i])
			j++;
		next[i] = j;
	}
}

inline int minim(int a, int b)
{	return a<=b?a:b;}

int main()
{
	FILE *f = fopen("strmatch.in","r");
	fscanf(f, "%s",a);
	fscanf(f, "%s",b);
	fclose(f);
	n = strlen(a);
	m = strlen(b);
	calc_next();

	int i,j = 0;
	for(i=0;i<m;i++)
	{
		while(j && b[i] != a[j])
			j = next[j];
		if( b[i] == a[j])
			j++;
		if(j==n)
		{
			j = next[n - 1];
			if(k < 1000)
				app[k++] = i - n +1;
		}
	}
	f = fopen("strmatch.out","w");
	fprintf(f, "%d\n",k);
	for(i=0;i< minim(1000,k);i++)
		fprintf(f, "%d ", app[i]);	
	fclose(f);		
	return 0;
}