Pagini recente » Cod sursa (job #1729130) | Istoria paginii grigore-moisil-2008/clasament/10 | Cod sursa (job #636680) | Cod sursa (job #194429) | Cod sursa (job #155372)
Cod sursa(job #155372)
# 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 ;
}