Cod sursa(job #488507)

Utilizator szabibibiOrban Szabolcs szabibibi Data 28 septembrie 2010 23:04:15
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
#include <string.h>


const long Nmax = 2000001;
const int meg = 1001;

char A[Nmax], B[Nmax];
long next[Nmax], pos[meg];

long n,m;
long N = 0;


void olvas();
void prefix();
void egyeb();
void kiir();



int main()
{
	olvas();
	prefix();
	egyeb();
	kiir();
	return 0;
}

void olvas()
{
	freopen("strmatch.in", "r", stdin);

	fgets(B, sizeof(B), stdin);
	fgets(A, sizeof(A), stdin);
	n = strlen(A);
	m = strlen(B);
	if (B[m-1] == '\n')
       m--;
	if (A[n-1] == '\n')
       n--;

	for (int i=n;i>0;i--)
		A[i] = A[i-1];
    A[0] = ' ';
	for (int i=m;i>0;i--)
		B[i] = B[i-1];
	B[0] = ' ';
}

void prefix()
{
	long k = 0;
	next[1] = 0;

	for (int q = 2; q<=m; q++)
	{
		while ((k) && (B[k+1] != B[q]))
			k = next[k];
		if (B[k+1] == B[q])
			k++;
		next[q] = k;
	}
}

void egyeb()
{
	long i = 0;
	long k = 0;
	while (++i<=n)
	{
        while ((k) && (B[k+1] != A[i]))
            k = next[k];
        if (B[k+1] == A[i])
            k++;
        if (k == m)
        {
            k = next[m];  
            ++N;
            if (N < meg) pos[N] = i-m;
        }
	}
}

void kiir()
{
    freopen("strmatch.out", "w", stdout);

    printf("%ld\n",N);
    long nn = N;
    if (N>=meg) nn = meg-1;
	for (int i = 1; i<= nn; i++)
        printf("%ld ", pos[i]);
}