Pagini recente » Cod sursa (job #2656585) | Cod sursa (job #978851) | Monitorul de evaluare | Cod sursa (job #1713226) | Cod sursa (job #1549646)
#include <fstream>
#include <cstring>
using namespace std;
#define NMAX 2000010
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char N[ NMAX ], M[ NMAX ];
int n,m,k,q,pi[ NMAX ],ans,v[1010],i;
int main()
{
fin.get( N + 1 , NMAX ); fin.get();
fin.get( M + 1 , NMAX );
N[ 0 ] = ' ';
M[ 0 ] = ' ';
n = strlen( N );
m = strlen( M );
for( i = 2 ; i <= n ; i++ )
{
while( k > 0 && N[ k + 1 ] != N[ i ] )
k = pi[ k ];
if( N[ k + 1 ] == N[ i ] )
k++;
pi[ i ] = k;
}
for( i = 1 ; i <= m ; i++ )
{
while( q > 0 && N[ q + 1 ] != M[ i ] )
q = pi[ q ];
if( N[ q + 1 ] == M[ i ] )
q++;
if( q == n - 1 )
{
++ans;
if( ans <= 1000 )
v[ ans ] = i - n + 1;
}
}
fout<<ans<<'\n';
for( i = 1 ; i <= min( ans , 1000 ) ; i++ )
fout<<v[ i ]<<' ';
return 0;
}