Pagini recente » Cod sursa (job #2777624) | Cod sursa (job #2238901) | Cod sursa (job #2863217) | Cod sursa (job #2558961) | Cod sursa (job #155453)
Cod sursa(job #155453)
# 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 ;
}