Cod sursa(job #159204)

Utilizator viktor0710Ardelean Cristian-Viktor viktor0710 Data 13 martie 2008 23:48:57
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
# include <stdio.h>
# include <string.h>
const 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 prefix ()
{
 int k = 0;

 p[1] = 0;
 for (int 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;
  }
}

void kmp ()
{
 int k = 0;
    for ( int i = 0; 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 <= nr; ++ i )
		printf ( "%d ", r[i] );
	fclose ( stdout );
}

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