Pagini recente » Cod sursa (job #477731) | Cod sursa (job #3171435) | Cod sursa (job #526466) | Cod sursa (job #1053802) | Cod sursa (job #812711)
Cod sursa(job #812711)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define B1 71
#define mod1 100021
#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 + 1;
}
}
printf("%d\n", v[0]);
for(int i = 1; i <= min(1001,v[0]); ++i)
printf("%d ", v[i] - 1);
return 0;
}