Pagini recente » Cod sursa (job #1472327) | Cod sursa (job #2743381) | Cod sursa (job #1141912) | Cod sursa (job #3260942) | Cod sursa (job #2482999)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD1 = 2000003, MOD2 = 2000029, BASE = 256, MAXS = 2000010, MAXN = 1000;
char str[MAXS], sub[MAXS];
int pos[MAXN], k, n, m, subHash1, subHash2, hash1, hash2, power1 = 1, power2 = 1;
void read() {
fin.getline(sub, MAXS);
fin.getline(str, MAXS);
n = strlen(str);
m = strlen(sub);
}
void calculateHashes() {
for (int i = 0; i < m; ++i) {
subHash1 = (subHash1 * BASE + sub[i]) % MOD1;
subHash2 = (subHash2 * BASE + sub[i]) % MOD2;
hash1 = (hash1 * BASE + str[i]) % MOD1;
hash2 = (hash2 * BASE + str[i]) % MOD2;
if (i) {
power1 = (power1 * BASE) % MOD1;
power2 = (power2 * BASE) % MOD2;
}
}
}
void solve() {
if (hash1 == subHash1 && hash2 == subHash2)
pos[k++] = 0;
for (int i = m; i < n; ++i) {
hash1 = ((hash1 - (str[i - m] * power1) % MOD1 + MOD1) * BASE + str[i]) % MOD1;
hash2 = ((hash2 - (str[i - m] * power2) % MOD2 + MOD2) * BASE + str[i]) % MOD2;
if (hash1 == subHash1 && hash2 == subHash2) {
if (k < 1000)
pos[k] = i - m + 1;
++k;
}
}
}
void print() {
fout << k << '\n';
if (k > 1000)
k = 1000;
for (int i = 0; i < k; ++i)
fout << pos[i] << ' ';
}
int main() {
read();
calculateHashes();
solve();
print();
return 0;
}