Pagini recente » Cod sursa (job #1749203) | Profil DalmatianuSebik | Cod sursa (job #2670567) | Monitorul de evaluare | Cod sursa (job #856738)
Cod sursa(job #856738)
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std ;
long sol [ 1007 ] ;
char a [ 2000007 ] , b [ 2000007 ] ;
long n , m , x ;
long p [ 2000007 ] ;
void fa_x ( char b [ ] ,long i )
{
while ( x > 0 && a [ x + 1 ] != b [ i ] )
x = p [ x ] ;
if ( a [ x + 1 ] == b [ i ] )
++ x ;
}
void make_prefix ( )
{
for ( long i = 2 ; i <= m ; ++ i )
{
fa_x ( a , i ) ;
p [ i ] = x ;
}
}
int main()
{
long nr2 = 0 ;
freopen ( "strmatch.in" , "r" , stdin ) ;
freopen ( "strmatch.out" , "w" , stdout ) ;
a [ 0 ] = ' ' ;
gets ( a + 1 ) ;
b [ 0 ] = ' ' ;
gets ( b + 1 ) ;
m = strlen ( a ) - 1 ;
n = strlen ( b ) - 1 ;
make_prefix ( ) ;
x = 0 ;
long ok = 0 ;
for( long i = 1 ; i <= n && ok == 0 ; ++ i )
{
fa_x ( b , i ) ;
if ( x == m )
{
x = p [ m ] ;
sol [ ++ sol [ 0 ] ] = i - m ;
if ( sol [ 0 ] == 1001 )
ok = 1 ;
}
}
long nr = 1000 ;
printf ( "%ld\n" , min ( nr , sol [ 0 ] ) ) ;
nr = 1000 ;
for( long i = 1 ; i <= min ( nr , sol [ 0 ] ) ; ++ i )
printf ( "%ld ", sol [ i ] ) ;
return 0 ;
}