Pagini recente » Istoria paginii runda/1112 | Istoria paginii runda/zbang1 | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #508714)
Cod sursa(job #508714)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int P1 = 1000021;
const int P2 = 1000007;
const int B1 = 3 ;
const int B2 = 5 ;
const int N = 2000007;
char a[N], b[N];
int n, m, val1, val2, sol[1005], nr;
int x, y, r, t;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i;
scanf("%s %s", &a, &b);
n = strlen(a);
m = strlen(b);
val1 = val2 = 1;
for( i = 0; i < n; ++i) {
x = ( x * B1 + a[i] ) % P1;
r = ( r * B2 + a[i] ) % P2;
if( i != 0) {
val1 = ( val1 * B1 ) % P1;
val2 = ( val2 * B2 ) % P2;
}
}
for ( i = 0; i < n; ++i ) {
y = ( y * B1 + b[i] ) % P1;
t = ( t * B2 + b[i] ) % P2;
}
b[m]='0'-1;
for( i = n; i <= m; ++i) {
if( x == y && r == t ) {
++nr;
if( nr <= 1000 )
sol[nr] = i - n ;
}
y = ( y - b[i-n] * val1 ) % P1 + P1; y = ( ( y * B1 ) + b[i] ) % P1 ;
t = ( t - b[i-n] * val2 ) % P2 + P2; t = ( ( t * B2 ) + b[i] ) % P2 ;
}
printf("%d\n", nr);
for( i = 1; i <= min( 1000, nr ); ++i)
printf("%d ",sol[i]);
return 0;
}