Pagini recente » Cod sursa (job #2716141) | Cod sursa (job #597053) | Cod sursa (job #1602486) | Cod sursa (job #847703) | Cod sursa (job #159253)
Cod sursa(job #159253)
# 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 );
fgets ( sub, MAX, stdin );sub[strlen(sub)-1] = 0;
fgets ( s, MAX, stdin );
n = strlen ( s ); m = strlen ( sub );
fclose ( stdin );
}
void kmp ()
{
int k = 0,i;
p[1] = 0;
for ( i = 2; i <= m;++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 <= n; ++i )
{
while ( k > 0 && sub[k] != s[i-1] )
k = p[k];
if ( sub[k] == s[i-1]) k++;
if ( k == m )
{
nr++;
if ( nr <= 1000 )
r[nr] = i - m;
}
}
}
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 ;
}