Pagini recente » Cod sursa (job #2616217) | Cod sursa (job #794239) | Cod sursa (job #3254844) | Cod sursa (job #2938444) | Cod sursa (job #864979)
Cod sursa(job #864979)
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std ;
vector < long > sol ;
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 . push_back ( i - m ) ;
}
}
long nr = 1000 ;
printf ( "%ld\n" , ( long ) sol . size ( ) ) ;
for( long i = 0 ; i < min ( nr , ( long ) sol . size ( ) ) ; ++ i )
printf ( "%ld ", sol [ i ] ) ;
return 0 ;
}