Pagini recente » Cod sursa (job #670079) | Cod sursa (job #1357052) | Cod sursa (job #966058) | Cod sursa (job #281380) | Cod sursa (job #3226919)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2e6;
const unsigned BASE = 37;
string a, b;
unsigned code(char c) {
if (c == '#')
return 53;
if (c == '%')
return 54;
if (c >= 'A' && c <= 'Z')
return c - 'A' + 1;
return 27 + c - 'a';
}
unsigned pref[2 * NMAX + 2];
unsigned pBase[NMAX + 2];
unsigned get_hash(int st, int dr) {
return pref[dr] - pref[st - 1] * pBase[dr - st + 1];
}
void solve() {
fin >> a >> b;
int sz = a.length();
a = "%" + a + "#" + b;
int ans = 0;
vector<int> pos;
pBase[0] = 1;
for (int i = 1; i <= sz; i++)
pBase[i] = pBase[i - 1] * BASE;
for (int i = 1; i < a.length(); i++) {
pref[i] = pref[i - 1] * BASE + code(a[i]);
}
unsigned firstHash = get_hash(1, sz);
for (int i = 2; i + sz - 1 < a.length(); i++) {
if (get_hash(i, i + sz - 1) == firstHash) {
ans++;
if (ans <= 1000)
pos.push_back(i - sz - 2);
}
}
fout << ans << '\n';
for (int & x : pos)
fout << x << ' ';
}
signed main() {
solve();
return 0;
}