Pagini recente » Cod sursa (job #362853) | Cod sursa (job #1087011) | Cod sursa (job #1905280) | Cod sursa (job #1323001) | Cod sursa (job #1081629)
#include <cassert>
#include <cstdio>
#include <cstring>
using namespace std;
const int nmax=2000000;
const int solmax= 1000;
int p[nmax+1], sol[solmax+1];
char a[nmax+1], b[nmax+1];
void prefix( int n ) {
int k= 0;
for ( int i= 2; i<=n; ++i ) {
while ( k>0 && a[k+1]!=a[i] ) {
k= p[k];
}
if (a[k+1]==a[i]) {
++k;
}
p[i]=k;
}
}
int main( ) {
assert( freopen( "strmatch.in", "r", stdin ) );
assert( freopen( "strmatch.out", "w", stdout) );
assert(scanf("%s%s",a+1,b+1));
int n=strlen(a+1), m=strlen(b+1);
prefix(n);
int k= 0, soln= 0;
for ( int i= 1; i<=m; ++i ) {
while ( k>0 && a[k+1]!=b[i] ) {
k= p[k];
}
if ( a[k+1]==b[i] ) {
++k;
}
if ( k==n ) {
++soln;
if ( soln<=solmax ) {
sol[soln]= i-n;
}
}
}
assert( printf( "%d\n", soln ) );
for ( int i= 1; i<=soln && i<=solmax; ++i ) {
assert( printf( "%d ", sol[i] ) );
}
assert( printf( "\n" ) );
return 0;
}