Pagini recente » Cod sursa (job #697070) | Cod sursa (job #2074934) | Cod sursa (job #118442) | Cod sursa (job #1742598) | Cod sursa (job #2750698)
#include <bits/stdc++.h>
#define ll long long
#define MOD 9987671
#define P 9981121
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
ll nr, pw = 1, orig, cur, cod[130];
vector <ll> pos;
int main() {
fin >> a >> b;
for (int i = '0'; i <= '9'; ++i)
cod[i] = ++nr;
for (int i = 'a'; i <= 'z'; ++i)
cod[i] = ++nr;
for (int i = 'A'; i <= 'Z'; ++i)
cod[i] = ++nr;
ll n = a.size();
for (int i = 1; i < n; ++i)
pw = pw * 64 % MOD;
for (int i = 0; i < n; ++i) {
orig = orig * 64 % MOD + cod[a[i]] % MOD;
cur = cur * 64 % MOD + cod[b[i]] % MOD;
}
if (orig == cur)
pos.push_back(0);
for (int i = n; i < b.size(); ++i) {
cur = ((cur - cod[b[i - n]] * pw % MOD + MOD) * 64 + cod[b[i]]) % MOD;
if (cur == orig && pos.size() < 1000)
pos.push_back(i - n + 1);
}
fout << pos.size() << "\n";
for (int i = 0; i < pos.size(); ++i)
fout << pos[i] << " ";
return 0;
}