Cod sursa(job #159179)

Utilizator viktor0710Ardelean Cristian-Viktor viktor0710 Data 13 martie 2008 23:35:03
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
# include <stdio.h>
# include <string.h>
char s[2000010], sub[2000010];
int p[2000010], n, m, r[1000],nr=0;

void cit ()
{
    freopen ( "strmatch.in", "r", stdin );
    fgets ( sub, 100, stdin );sub[strlen(sub)-1] = 0;
    fgets ( s, 100, stdin );
    n = strlen ( s ); m = strlen ( sub );
    fclose ( stdin );
}

void prefix ()
{
 int j = -1;

 p[0] = -1;
 for (int i = 0; i < m; )
  {
	while ( j >= 0 && sub[i] != sub[j] )
		j = p[j];
	++j; ++i;
	if ( sub[j]==sub[i] )
		p[i] = p[j];
	else
		p[i] = j;
  }
}

void kmp ()
{
 int j = 0;
    for ( int i = 0; i < n;  )
	{
	    while ( j > -1 && s[i] != sub[j] )
		j = p[j];
	    ++i; ++j;
	    if  ( j >= m )
	     {
		nr++;
		if ( nr <= 1000 )
			r[nr] = i - j;
		j = p[j];
	     }
	}
}

void afis ()
{
	freopen ( "strmatch.out", "w", stdout );
	printf ( "%d\n", nr );
	for ( int i = 1; i <= nr; ++ i )
		printf ( "%d ", r[i] );
	fclose ( stdout );
}

int main ()
{
	cit();
	prefix();
	freopen ( "strmatch.out", "w", stdout );
	kmp();
	afis ();
	fclose ( stdout );
	return 0 ;
}