Cod sursa(job #155388)

Utilizator viktor0710Ardelean Cristian-Viktor viktor0710 Data 11 martie 2008 21:44:07
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
# include <stdio.h>
# include <string.h>

char s[10000000], sub[21], chr[21][50000];
int p[22], n, m, nr = 0, num = -1;


int verif ()
{
	for ( int i = 0; i <= num; ++i )
		if ( strcmp(chr[i], sub) == 0 )
			return 0;
	strcpy ( chr[i], sub ); ++ num;
	return 1;
}

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++;
		j = p[j];
	     }
	}
}

void exe ()
{
    freopen ( "abc2.in", "r", stdin );
    freopen ( "abc2.out", "w", stdout );
    fgets ( s, 10000000, stdin );
    if ( s[strlen (s)-1] == '\n' )
	s[strlen(s)-1] = 0;
    n = strlen ( s );
    while ( !feof(stdin ) )
     {
	fgets ( sub, 22, stdin );
	if ( sub[strlen (sub)-1] == '\n' )
		sub[strlen(sub)-1] = 0;
	if (verif ())
	 {
		m = strlen ( sub );
		prefix ();
		kmp();
	 }
     }
    printf ( "%d", nr );
    fclose ( stdout );
    fclose ( stdin );
}


int main ()
{
	exe();
	return 0 ;
}