Pagini recente » Cod sursa (job #177987) | Cod sursa (job #966026) | Cod sursa (job #2000956) | Cod sursa (job #987139) | Cod sursa (job #3200413)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMAX 2000005
#define MOD1 100007
#define MOD2 100021
#define b1 101
#define b2 103
char a[NMAX], b[NMAX];
int rez[1005];
int main() {
fin >> a >> b;
int l1 = strlen(a), l2 = strlen(b);
if (l1 > l2) {
fout << 0;
return 0;
}
int h1 = 0, h2 = 0;
for (int i = 0; i < l1; ++i) {
h1 = (h1 * b1 + a[i]) % MOD1;
h2 = (h2 * b2 + a[i]) % MOD2;
}
int hash1 = 0, hash2 = 0;
int putere1 = 1, putere2 = 1;
for (int i = 0; i < l1; ++i) {
hash1 = (hash1 * b1 + b[i]) % MOD1;
hash2 = (hash2 * b2 + b[i]) % MOD2;
if (i != 0) {
putere1 *= b1;
putere2 *= b2;
putere1 %= MOD1;
putere2 %= MOD2;
}
}
int nr = 0;
int cnt = 0;
if (h1 == hash1 && h2 == hash2) {
rez[++cnt] = 0;
}
for (int i = l1; i < l2; ++i) {
hash1 = ((hash1 - b[i - l1] * putere1 % MOD1 + MOD1) % MOD1 * b1 % MOD1 + b[i]) % MOD1;
hash2 = ((hash2 - b[i - l1] * putere2 % MOD2 + MOD2) % MOD2 * b2 % MOD2 + b[i]) % MOD2;
if (h1 == hash1 && h2 == hash2) {
nr++;
if (cnt < 1000) {
rez[++cnt] = i - l1 + 1;
}
}
}
fout << nr << '\n';
for (int i = 1; i <= cnt; ++i) {
fout << rez[i] << ' ';
}
return 0;
}