Pagini recente » Cod sursa (job #2595166) | Cod sursa (job #2792987) | Cod sursa (job #705547) | Cod sursa (job #2110636) | Cod sursa (job #812694)
Cod sursa(job #812694)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define B1 71
#define mod1 666001
#define mod2 100007
const int MAXN = 2000005;
using namespace std;
char A[MAXN], B[MAXN];
int n, m, hash1, hash2, H1, H2;
int v[1005];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", A + 1); n = strlen(A + 1);
scanf("%s\n", B + 1); m = strlen(B + 1);
int P1 = 1, P2 = 1;
for(int i = 1; i <= n; ++i) {
hash1 = (hash1 * B1 + A[i]) % mod1;
hash2 = (hash2 * B1 + A[i]) % mod2;
P1 = (P1 * B1) % mod1;
P2 = (P2 * B1) % mod2;
}
// printf("%d %d\n", P1, P2);
for(int i = 1; i <= n; ++i) {
H1 = (H1 * B1 + B[i]) % mod1;
H2 = (H2 * B1 + B[i]) % mod2;
}
if(H1 == hash1 && H2 == hash2)
v[++v[0]] = 1;
for(int i = n + 1; i <= m; ++i) {
H1 = (H1 * B1 + B[i]) % mod1;
H2 = (H2 * B1 + B[i]) % mod2;
H1 = (H1 - (B[i - n] * P1) % mod1 + mod1) % mod1;
H2 = (H2 - (B[i - n] * P2) % mod2 + mod2) % mod2;
//printf("%d %d %d %d\n", hash1, H1, hash2, H2);
if(H1 == hash1 && H2 == hash2) {
++v[0];
if(v[0] >= 1000) continue;
v[v[0]] = i - n;
}
}
printf("%d\n", v[0]);
for(int i = 1; i <= min(1000,v[0]); ++i)
printf("%d ", v[i]);
return 0;
}