Cod sursa(job #159260)

Utilizator viktor0710Ardelean Cristian-Viktor viktor0710 Data 14 martie 2008 00:23:47
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 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 );
    fclose ( stdin );
}

void kmp ()
{
 int k = 0,i;
 m = strlen ( s ); n = strlen ( sub );
 p[1] = 0;
 for ( i = 2; i <= n;++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 <= m; ++i  )
     {
	    while ( k > 0 && sub[k] != s[i-1] )
		k = p[k];
	    if ( sub[k] == s[i-1]) ++k;
	    if  ( k == n )
	     {
		nr++;
		if ( nr <= 1000 )
			r[nr] = i - n;
	     }
     }
}

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 ;
}