Pagini recente » Cod sursa (job #2566586) | Cod sursa (job #2570005) | Cod sursa (job #2217919) | Cod sursa (job #2107516) | Cod sursa (job #2021227)
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
using namespace std;
const unsigned long long base = 197;
const int MAX = 2e6 + 14;
void hsh(string a, unsigned long long &hash_a) {
unsigned long long p = 1;
for (auto x : a) {
hash_a += (x - '0') * 1ull * p;
p *= base;
}
}
bitset < MAX > found_at;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string a, b;
cin >> a >> b;
unsigned long long hash_a = 0;
hsh(a, hash_a);
vector < unsigned long long > h(b.size() + 14);
vector < unsigned long long > base_pow(b.size() + 14);
base_pow[0] = 1;
for (int i = 1; i <= b.size(); i ++) {
base_pow[i] = base_pow[i - 1] * base;
}
for (int i = b.size() - 1; i >= 0; i --) {
h[i] = h[i + 1] * base + (b[i] - '0') * 1ull;
}
int cnt = 0;
for (int i = 0; i <= b.size() - a.size(); i ++) {
if (hash_a == (h[i] - (h[i + a.size()] * base_pow[a.size()]))) {
cnt ++;
found_at[i] = true;
}
}
cout << cnt << '\n';
for (int i = 0; i <= b.size(); i ++) {
if (found_at[i]) {
cout << i << ' ';
}
}
}