Pagini recente » Cod sursa (job #2182612) | Cod sursa (job #24332) | Cod sursa (job #2816272) | Cod sursa (job #1921583) | Cod sursa (job #2791392)
#include <iostream>
#include <cstring>
using namespace std;
const int NMAX = 2000000;
int sl, micutl, ans[1005], ansl;
char s[NMAX + 5], micut[NMAX + 5];
struct Hash {
long long n = 97, m = 0, power = 0, value = 0, sl, i;
char * s;
Hash(char * X, const int XL, const int M) {
s = X;
sl = XL;
i = sl;
m = M;
power = 1;
value = 0;
for(int i = sl - 1; i >= 0; --i) {
value = (value + power * s[i] % m) % m;
if(i) power = power * n % m;
}
}
void roll() {
value = (((value - (1ll * s[i - sl] * power) % m + m) * n) % m + s[i]) % m;
++i;
}
};
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", micut, s);
micutl = strlen(micut), sl = strlen(s);
if(micutl > sl) {
printf("0");
return 0;
}
Hash mh1 = Hash(micut, micutl, 100003),
mh2 = Hash(micut, micutl, 100019),
sh1 = Hash(s, micutl, 100003),
sh2 = Hash(s, micutl, 100019);
for(int i = micutl - 1; i < sl; ++i) {
if(sh1.value == mh1.value && sh2.value == mh2.value) {
++ansl;
if(ansl <= 1000) ans[ansl] = i - micutl + 1;
}
sh1.roll(),
sh2.roll();
}
printf("%d\n", ansl);
ansl = min(ansl, 1000);
for(int i = 1; i <= ansl; ++i) {
printf("%d ", ans[i]);
}
return 0;
}