Pagini recente » Cod sursa (job #867778) | Cod sursa (job #2819942) | Cod sursa (job #2237453) | Cod sursa (job #1798917) | Cod sursa (job #2021234)
#include <fstream>
#include <vector>
#include <string>
#include <bitset>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
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() {
string a, b;
cin >> a >> b;
unsigned long long hash_a = 0;
hsh(a, hash_a);
vector < unsigned long long > h(b.size() + 14);
unsigned long long pow_as = 1;
for (int i = 1; i <= a.size(); i ++) {
pow_as *= base;
}
for (int i = b.size() - 1; i >= 0; i --) {
h[i] = h[i + 1] * base + 1ull * (b[i] - '0');
}
int cnt = 0;
for (int i = 0; i <= b.size() - a.size(); i ++) {
if (hash_a == (h[i] - (h[i + a.size()] * pow_as))) {
cnt ++;
found_at[i] = true;
}
}
cout << cnt << '\n';
cnt = 0;
for (int i = 0; i <= b.size(); i ++) {
if (found_at[i]) {
if (++ cnt > 1000) return 0;
cout << i << ' ';
}
}
}