Cod sursa(job #159253)

Utilizator viktor0710Ardelean Cristian-Viktor viktor0710 Data 14 martie 2008 00:19:31
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
# include <stdio.h>
# include <string.h>
const int MAX = 2000001;
char s[MAX], sub[MAX];
int p[MAX], n, m, r[1024],nr=0;

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

void kmp ()
{
 int k = 0,i;
 p[1] = 0;
 for ( i = 2; i <= m;++i )
  {
	while ( k > 0 && sub[k] != sub[i-1] )
		k = p[k];
	if ( sub[k]==sub[i-1] )
		k++;
	p[i] = k;
  }

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

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

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