Pagini recente » Cod sursa (job #2325940) | Cod sursa (job #2087647) | Cod sursa (job #1756020) | Cod sursa (job #194673) | Cod sursa (job #335305)
Cod sursa(job #335305)
#include <algorithm>
using namespace std;
#define DIM 2000001
#define MAX 1000
int n, m, rez, pi[ DIM ], sol[ DIM ];
char a[ DIM ], b[ DIM ];
void calc_pi() {
int i, k;
k = 0;
for( i = 2; i <= n; ++ i ) {
while( a[ k + 1 ] != a[ i ] && k )
k = pi[ k ];
if( a[ k + 1 ] == a[ i ] )
++ k;
pi[ i ] = k;
}
}
void kmp() {
int i, k;
k = 0;
for( i = 1; i <= m; ++ i ) {
while( a[ k + 1 ] != b[ i ] && k )
k = pi[ k ];
if( a[ k + 1 ] == b[ i ] )
++ k;
if( k == n ) {
k = pi[ n ];
sol[ ++ rez ] = i - n;
if( rez == MAX )
return;
}
}
}
void solve() {
int i, k;
gets( a + 1 );
n = strlen( a + 1 );
gets( b + 1 );
m = strlen( b + 1 );
calc_pi();
kmp();
printf( "%d\n", rez );
for( i = 1; i <= rez; ++ i )
printf( "%d ", sol[ i ] );
}
int main() {
freopen( "strmatch.in", "r", stdin );
freopen( "strmatch.out", "w", stdout );
solve();
return 0;
}