Cod sursa(job #155453)

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

char s[100], sub[22], chr[50][22];
int p[22], n, m, nr = 0, num = -1;


int verif ()
{
 long st = 0, dr = num, mij ;
	while ( st <= dr )
	 {
		if ( st == dr )
			if (strcmp(chr[st],sub)==0  )
				return 0;
			else
			 break;
		mij = (st+dr)/2;
		if ( strcmp(chr[mij], sub) == 0 )
			return 0;
		else
		 if ( strcmp(chr[mij], sub) < 0 )
			st = mij+1;
		 else
		  if ( strcmp(chr[mij], sub) > 0 )
			dr = mij-1;

	 }
	int i;
	for ( i = num; i>=0 && strcmp(sub,chr[i]) < 0; i-- )
		strcpy ( chr[i+1], chr[i] );
	strcpy ( chr[i+1], 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, 100, 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 ;
}