Pagini recente » Cod sursa (job #1873871) | Cod sursa (job #1007128) | Cod sursa (job #2742347) | Cod sursa (job #1267616) | Cod sursa (job #1526847)
#include<cstdio>
#include<string.h>
#define baza 127
#define mod1 100007
#define mod2 100021
#define strl 2000001
char a[strl], b[strl], o[5001];
int hashA1, hashA2, hashB1, hashB2;
long long p1, p2;
char pot[strl];
int nrpot;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", a, b);
int la = strlen(a), lb = strlen(b);
if(la>lb) {
printf("0\n");
return 0;
}
int i;
p1 = p2 = 1;
for(i=0; i<la; i++) {
hashA1 = (hashA1 * baza + a[i]) % mod1;//Calcules hash-urile sirului A
hashA2 = (hashA2 * baza + a[i]) % mod2;
hashB1 = (hashB1 * baza + b[i]) % mod1;//Calcules hash-urile primei parti a sirului B A
hashB2 = (hashB2 * baza + b[i]) % mod2;
if(i!=0)
p1 = (p1 * baza) % mod1,
p2 = (p2 * baza) % mod2;
}
if(hashB1 == hashA1 && hashB2 == hashA2) pot[0] = 1, nrpot = 1;
for(i=la; i<lb; i++) {
if(hashB1 == hashA1 && hashB2 == hashA2) pot[i-la] = 1, nrpot++;
hashB1 = ((hashB1 - (b[i-la] * p1) % mod1 + mod1) * baza + b[i]) % mod1;
hashB2 = ((hashB2 - (b[i-la] * p2) % mod2 + mod2) * baza + b[i]) % mod2;
}
printf("%d\n", nrpot);
nrpot = 0;
for (int i = 0; i < lb && nrpot < 1000; i++)
if (pot[i])
nrpot++,
printf("%d ", i);
return 0;
}