Cod sursa(job #1468722)

Utilizator enacheionutEnache Ionut enacheionut Data 6 august 2015 19:49:55
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.03 kb
#include<stdio.h>
#include<string.h>

#define MAX 2000000
char A[MAX],B[MAX];
int pi[MAX],sol[1005],n,m,total;

void buildPrefix()
{
	int i, q = 0;

	for (i = 2, pi[1] = 0; i <= m; i++){
		while ( q && A[q+1] != A[i] )
			q = pi[q];
		if (A[q+1] == A[i]){
			q++;
        }
		pi[i] = q;
	}
}

void solve()
{
	int q = 0,i;
	for ( i = 1; i <= n; ++i)
	{
		while (q && A[q+1] != B[i])
			q = pi[q];
		if (A[q+1] == B[i])
			++q;
		if (q == m)
		{
			q = pi[m];
			if(total < 1000)
				sol[total] = i-m;
			total++;
		}
	}
}

void show()
{
    int i;
	printf("%d\n",total);
	for( i = 0; i < (total < 1000 ? total : 1000); i++)
		printf("%d ",sol[i]);
}

int main()
{
	freopen("potrivire.in","r",stdin);
	freopen("potrivire.out","w",stdout);

	scanf("%s %s",&A,&B);
	m = strlen(A+1);
    n = strlen(B+1);

	if(m > n){
        printf( "Subsirul %s nu se gaseste in sirul %s \n",A,B );
        return 0;
    }
	buildPrefix();
	solve();
	show();

	fclose(stdin);
    fclose(stdout);

	return 0;
}