Pagini recente » Cod sursa (job #244941) | Cod sursa (job #3224595) | Cod sursa (job #2544590) | Cod sursa (job #2548812) | Cod sursa (job #2791131)
#include <iostream>
#include <cstring>
using namespace std;
const int NMAX = 2000003;
int sl, micutl, ans[1010], ansl;
char s[NMAX + 1], micut[NMAX + 1];
class Hash {
private:
long long n = 97, m = 666013, power = 0;
public:
long long value = 0;
Hash() {
power = value = 0;
}
void init(const char * X, const int XL, const int M) {
m = M;
power = 1;
value = 0;
for(int i = XL; i; --i) {
value = (value + power * X[i] % m) % m;
if(i - 1) power = power * n % m;
}
}
void roll(const char toRem, const char toAdd) {
value = (((value - (1ll * toRem * power) % m + m) * n) % m + toAdd) % m;
}
};
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", micut + 1, s + 1);
micutl = strlen(micut + 1), sl = strlen(s + 1);
if(micutl > sl) {
printf("0");
return 0;
}
Hash mh1, mh2, sh1, sh2;
mh1.init(micut, micutl, 100003);
mh2.init(micut, micutl, 100019);
sh1.init(s, micutl, 100003);
sh2.init(s, micutl, 100019);
for(int i = micutl; i <= sl; ++i) {
if(sh1.value == mh1.value && sh2.value == mh2.value) {
++ansl;
if(ansl <= 1000) ans[ansl] = i - micutl;
}
if(i < sl)
sh1.roll(s[i - micutl + 1], s[i + 1]),
sh2.roll(s[i - micutl + 1], s[i + 1]);
}
printf("%d\n", ansl);
ansl = min(ansl, 1000);
for(int i = 1; i <= ansl; ++i) {
printf("%d ", ans[i]);
}
return 0;
}