Pagini recente » Cod sursa (job #685351) | Monitorul de evaluare | Cod sursa (job #2308812) | Cod sursa (job #2498249) | Cod sursa (job #1268108)
#include<cstdio>
using namespace std;
FILE *fin = fopen( "strmatch.in", "r" ), *fout = fopen( "strmatch.out", "w" );
const int nmax = 2000000;
const int nrsol = 1000;
int n, m, pi[ nmax + 1 ], sol[ nrsol ];
char a[ nmax + 1 ], b[ nmax + 1 ];
void citire() {
char x;
x = fgetc( fin );
n = m = 0;
while ( (x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z') || (x >= '0' && x <= '9') ) {
a[ ++ m ] = x;
x = fgetc( fin );
}
while ( !(x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z') || (x >= '0' && x <= '9') ) {
x = fgetc( fin );
}
do {
b[ ++ n ] = x;
x = fgetc( fin );
} while ( (x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z') || (x >= '0' && x <= '9') );
}
int main() {
int r, ans;
citire();
pi[ 1 ] = 0;
for( int i = 2; i <= m; ++ i ) {
r = pi[ i - 1 ];
while ( r != 0 && a[ r + 1 ] != a[ i ] ) {
r = pi[ r ];
}
if ( a[ r + 1 ] == a[ i ] ) {
pi[ i ] = r + 1;
} else {
pi[ i ] = 0;
}
}
ans = 0;
r = 0;
for( int i = 1; i <= n; ++ i ) {
while ( r != 0 && a[ r + 1 ] != b[ i ] ) {
r = pi[ r ];
}
if ( a[ r + 1 ] == b[ i ] ) {
++ r;
}
if ( r == m ) {
sol[ ans ++ ] = i - m + 1;
}
}
fprintf( fout, "%d\n", ans );
for( int i = 0; i < ans && i < nrsol; ++ i ) {
fprintf( fout, "%d ", sol[ i ] - 1 );
}
fclose( fin );
fclose( fout );
return 0;
}