Pagini recente » Cod sursa (job #55638) | Cod sursa (job #3175114) | Cod sursa (job #2189258) | Cod sursa (job #1601780) | Cod sursa (job #2768805)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD = 1e9 + 7;
const int P = 52;
vector<int>value(123), ans;
int N, M, ha, hb, p = 1, cnt;
string a, b;
int main() {
fin >> a >> b;
N = a.size();
M = b.size();
if(N > M) {
fout << "0\n";
return 0;
}
for(int i = 'A'; i <= 'Z'; i++) {
value[i] = i - 'A';
}
for(int i = 'a'; i <= 'z'; i++) {
value[i] = i - 'a' + 26;
}
for(int i = 0; i < N; i++) {
ha = (1LL * ha * P + value[a[i]]) % MOD;
if(i != N - 1) {
p = (1LL * p * P) % MOD;
}
}
for(int i = 0; i < N; i++) {
hb = (1LL * hb * P + value[b[i]]) % MOD;
}
if(hb == ha) {
ans.push_back(0);
}
// cout << ha << '\n' << hb << "\n\n";
for(int i = N; i < M; i++) {
int over = (1LL * value[b[i - N]] * p) % MOD;
hb = (hb - over + MOD) % MOD;
hb = (1LL * hb * P) % MOD;
hb = (hb + value[b[i]]) % MOD;
if(hb == ha) {
cnt++;
}
if(cnt <= 1000) {
ans.push_back(i - N + 1);
}
// cout << hb << '\n';
}
fout << cnt << '\n';
for(auto it: ans) {
fout << it << " ";
}
fout << '\n';
return 0;
}