Cod sursa(job #155372)

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

typedef struct nod {
	char str[21];
	nod* next;
		   };

char s[10000000], sub[21];
int p[22], n, m, nr = 0;
nod *w = NULL;


int verif ()
{
	if ( w == NULL )
		{
			w = new nod;
			strcpy ( w->str, sub );
			w->next = NULL;
		}
	else
	 {
	  for (nod *q = w; q; q = q->next )
		if (strcmp( q->str, sub ) == 0 )
			return 0;
	  nod* e; e= new nod;
	  strcpy ( e->str, sub );
	  e->next = w;
	  w = e;
	 }
	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, 100, 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 ;
}