Pagini recente » Cod sursa (job #2886851) | Cod sursa (job #2333798) | Cod sursa (job #323232) | Cod sursa (job #1201209) | Cod sursa (job #3199475)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NM = 2e6 + 5;
const int mod = 666013;
int p[NM];
int hs, ht[NM], inv[NM];
string s, t;
int n, m;
int pw (int a, int b) {
int p = 1;
while (b > 0) {
if (b % 2 == 1) {
p = 1LL * p * a % mod;
}
a = 1LL * a * a % mod;
b >>= 1;
}
return p;
}
int main() {
fin >> s >> t;
n = (int)s.size();
m = (int)t.size();
if (n > m) {
fout << 0;
return 0;
}
p[0] = 1;
inv[0] = pw(p[0], mod - 2);
for (int i = 1; i < NM; i++) {
p[i] = 1LL * p[i - 1] * 31 % mod;
inv[i] = pw(p[i], mod - 2);
}
for (int i = 0; i < n; i++) {
hs = (hs + 1LL * p[i + 1] * (s[i] - 'A' + 1) % mod) % mod;
}
for (int i = 0; i < m; i++) {
ht[i + 1] = (ht[i] + 1LL * p[i + 1] * (t[i] - 'A' + 1) % mod) % mod;
}
vector<int>pos;
for (int i = n; i <= m; i++) {
int Q = 1LL * (ht[i] - ht[i - n] + mod) % mod * inv[i - n] % mod;
if (hs == Q) {
pos.push_back(i - n);
}
}
fout << (int)pos.size() << '\n';
for (int i = 0; i < min(1000, (int)pos.size()); i++) {
fout << pos[i] << " ";
}
}