Pagini recente » Cod sursa (job #2862130) | Cod sursa (job #1266627) | Cod sursa (job #746174) | Cod sursa (job #1335443) | Cod sursa (job #159262)
Cod sursa(job #159262)
# include <stdio.h>
# include <string.h>
const int MAX = 2000001;
char s[MAX], sub[MAX];
int p[MAX], n, m, r[1024],nr=0;
void cit ()
{
freopen ( "strmatch.in", "r", stdin );
scanf ( "%s %s", sub, s );
fclose ( stdin );
}
void kmp ()
{
int k = 0,i;
m = strlen ( s ); n = strlen ( sub );
p[1] = 0;
for ( i = 2; i <= n;++i )
{
while ( k > 0 && sub[k] != sub[i-1] )
k = p[k];
if ( sub[k]==sub[i-1] )
++k;
p[i] = k;
}
k = 0;
for ( i = 1; i <= m; ++i )
{
while ( k > 0 && sub[k] != s[i-1] )
k = p[k];
if ( sub[k] == s[i-1]) ++k;
if ( k == n )
{
nr++;
if ( nr <= 1000 )
r[nr] = i - n;
}
}
}
void afis ()
{
freopen ( "strmatch.out", "w", stdout );
printf ( "%d\n", nr );
for ( int i = 1; i<=1000&&i <= nr; ++ i )
printf ( "%d ", r[i] );
fclose ( stdout );
}
int main ()
{
cit();
freopen ( "strmatch.out", "w", stdout );
kmp();
afis ();
fclose ( stdout );
return 0 ;
}