Pagini recente » Cod sursa (job #1745327) | Cod sursa (job #1361592) | Cod sursa (job #1453058) | Cod sursa (job #2673196) | Cod sursa (job #3200396)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MOD1 666013
#define MOD2 1000007
#define b1 101
#define b2 103
string a, b;
int rez[1005];
int main() {
fin >> a >> b;
int h1 = 0, h2 = 0;
for (auto it : a) {
h1 = (h1 * b1 + it) % MOD1;
h2 = (h2 * b2 + it) % MOD2;
}
int l1 = a.size(), l2 = b.size();
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 cnt = 0;
if (h1 == hash1 && h2 == hash2) {
rez[++cnt] = 0;
}
int i = 0;
for (int j = l1; j < l2; ++j) {
hash1 = ((hash1 - b[i] * putere1 + MOD1) % MOD1 * b1 + b[j]) % MOD1;
hash2 = ((hash2 - b[i] * putere2 + MOD2) % MOD2 * b2 + b[j]) % MOD2;
i++;
if (h1 == hash1 && h2 == hash2 && cnt < 1000) {
rez[++cnt] = i;
}
}
fout << cnt << '\n';
for (int i = 1; i <= cnt; ++i) {
fout << rez[i] << ' ';
}
return 0;
}