Pagini recente » Cod sursa (job #190771) | Cod sursa (job #1133906) | Istoria paginii runda/test_10 | Cod sursa (job #374347) | Cod sursa (job #1394846)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define mx 2000069
char A[mx] , B[mx] ;
int pi[mx] , pos[1069] ;
int a , b ;
void prefix()
{
int q = 0 ;
pi[1] = 0 ;
for ( int i = 2 ; i <= a ; i ++ )
{
while ( q && A[q+1] != A[i] )
q = pi[q] ;
if ( A[q+1] == A[i] )
q ++ ;
pi[i] = q ;
}
}
int main()
{
freopen( "strmatch.in" , "r" , stdin ) ;
freopen( "strmatch.out" , "w" , stdout ) ;
scanf( "%s" , A + 1 ) ;
a = strlen(A+1) ;
scanf( "%s" , B + 1 ) ;
b = strlen(B+1) ;
prefix() ;
int q = 0 , n = 0 ;
for ( int i = 1 ; i <= b; i ++ )
{
while ( q && A[q+1] != B[i] )
q = pi[q] ;
if ( A[q+1] == B[i] )
q ++ ;
if ( q == a )
{
q = pi[a] ;
n ++ ;
if ( n <= 1000 )
pos[n] = i - a ;
}
}
printf( "%d\n" , n ) ;
for ( int i = 1 ; i <= min(n,1000) ; i ++ )
printf( "%d " , pos[i] ) ;
return 0;
}