Pagini recente » Cod sursa (job #2691249) | Cod sursa (job #2541958) | Cod sursa (job #3149814) | Cod sursa (job #943861) | Cod sursa (job #2725688)
#include <stdio.h>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
// const int INF = 0x3f3f3f3f;
const int p = 73;
const int mod1 = 100'007;
const int mod2 = 100'021;
ifstream fin {"strmatch.in"};
ofstream fout {"strmatch.out"};
int main(void) {
// freopen("strmatch.in", "r", stdin);
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
string A, B;
fin >> A >> B;
int N = A.size(), M = B.size();
if (N > M) {
fout << "0\n";
return 0;
}
int ha1 = 0, ha2 = 0, hb1 = 0, hb2 = 0;
int p1 = 1, p2 = 1;
for(int i = 0; i < N; i++) {
ha1 = (ha1 * p + A[i]) % mod1;
ha2 = (ha2 * p + A[i]) % mod2;
hb1 = (hb1 * p + B[i]) % mod1;
hb2 = (hb2 * p + B[i]) % mod2;
p1 = (p1 * p) % mod1;
p2 = (p2 * p) % mod2;
}
vi res {};
int ans = 0;
if (ha1 == hb1 && ha2 == hb2) {
ans ++;
res.push_back(0);
}
for(int i = N; i < M; i++) {
hb1 = (hb1 * p + B[i]) % mod1 - (B[i-N] * p1) % mod1;
hb1 += (hb1 < 0 ? mod1 : 0);
hb2 = (hb2 * p + B[i]) % mod2 - (B[i-N] * p2) % mod2;
hb2 += (hb2 < 0 ? mod2 : 0);
if (ha1 == hb1 && ha2 == hb2) {
ans++;
if (ans <= 1000)
res.push_back(i-N+1);
}
}
fout << ans << '\n';
for(auto x: res)
fout << x << ' ';
fout << '\n';
return 0;
}