Pagini recente » Cod sursa (job #3353249) | Cod sursa (job #3354393) | Cod sursa (job #848940) | Borderou de evaluare (job #123996) | Cod sursa (job #3333370)
#include <bits/stdc++.h>
using namespace std;
static const long long MOD = 1000000007;
static const long long BASE = 131;
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
fin >> A >> B;
int n = A.size();
int m = B.size();
if (n > m) {
fout << 0 << "\n";
return 0;
}
vector<long long> power(m + 1);
power[0] = 1;
for (int i = 1; i <= m; i++)
power[i] = (power[i - 1] * BASE) % MOD;
vector<long long> hashB(m + 1, 0);
for (int i = 0; i < m; i++)
hashB[i + 1] = (hashB[i] * BASE + B[i]) % MOD;
long long hashA = 0;
for (char c : A)
hashA = (hashA * BASE + c) % MOD;
vector<int> positions;
for (int i = 0; i + n <= m; i++) {
long long currentHash =
(hashB[i + n] - (hashB[i] * power[n]) % MOD + MOD) % MOD;
if (currentHash == hashA) {
if (B.substr(i, n) == A) {
positions.push_back(i);
}
}
}
fout << positions.size() << "\n";
for (int i = 0; i < (int)positions.size() && i < 1000; i++) {
fout << positions[i] << " ";
}
fout << "\n";
return 0;
}