Pagini recente » Cod sursa (job #2137805) | Cod sursa (job #1926554) | stargold | Cod sursa (job #1706082) | Cod sursa (job #508958)
Cod sursa(job #508958)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int P1 = 1000021;
const int P2 = 1000007;
const int B1 = 101 ;
const int B2 = 103 ;
const int N = 2000007;
char a[N], b[N], o[N];
int n, m, val1, val2, 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;
o[i-n]=1;
}
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);
nr = 0;
for( i = 0; i< m && nr <= 1000; ++i )
if( o[i] )
++nr, printf("%d ",i);
return 0;
}