Pagini recente » Cod sursa (job #159465) | Cod sursa (job #2041546) | Cod sursa (job #1266054) | Cod sursa (job #2800014) | Cod sursa (job #155368)
Cod sursa(job #155368)
# 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;
q = new nod;
strcpy ( q->str, sub );
q->next = w;
w = q;
}
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 ;
}