Pagini recente » Cod sursa (job #1893296) | Cod sursa (job #1251994) | Cod sursa (job #741239) | Cod sursa (job #149003) | Cod sursa (job #159179)
Cod sursa(job #159179)
# include <stdio.h>
# include <string.h>
char s[2000010], sub[2000010];
int p[2000010], n, m, r[1000],nr=0;
void cit ()
{
freopen ( "strmatch.in", "r", stdin );
fgets ( sub, 100, stdin );sub[strlen(sub)-1] = 0;
fgets ( s, 100, stdin );
n = strlen ( s ); m = strlen ( sub );
fclose ( stdin );
}
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++;
if ( nr <= 1000 )
r[nr] = i - j;
j = p[j];
}
}
}
void afis ()
{
freopen ( "strmatch.out", "w", stdout );
printf ( "%d\n", nr );
for ( int i = 1; i <= nr; ++ i )
printf ( "%d ", r[i] );
fclose ( stdout );
}
int main ()
{
cit();
prefix();
freopen ( "strmatch.out", "w", stdout );
kmp();
afis ();
fclose ( stdout );
return 0 ;
}