Pagini recente » Cod sursa (job #1566285) | Rating Florin Popescu (floryn35) | Simulare 40 | Cod sursa (job #2806880) | Cod sursa (job #856750)
Cod sursa(job #856750)
#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 ] ;
if ( sol [ 0 ] < 1000 )
sol [ ++ sol [ 0 ] ] = i - m ;
if ( sol [ 0 ] == 1000 )
ok = 1 ;
}
}
printf ( "%ld\n" , sol [ 0 ] ) ;
for( long i = 1 ; i <= sol [ 0 ] ; ++ i )
printf ( "%ld ", sol [ i ] ) ;
return 0 ;
}