Pagini recente » Cod sursa (job #3319487) | Cod sursa (job #664353) | Cod sursa (job #2187744) | Cod sursa (job #2780211) | Cod sursa (job #3318141)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000005;
const long long BASE = 100;
const long long MOD = 1000000007;
const char HASHER = '0';
char A[NMAX], B[NMAX];
long long powers[NMAX];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void PrecomputePowers(int n) {
powers[0] = 1;
for (int i = 1; i <= n; i++)
powers[i] = (powers[i - 1] * BASE) % MOD;
}
long long HashEntireString(const char s[], int n) {
long long h = 0;
for (int i = 0; i < n; i++)
h = (h * BASE + (s[i] - HASHER)) % MOD;
return h;
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
fin >> A >> B;
int n = strlen(A), m = strlen(B);
if (m < n) {
fout << 0 << "\n";
return 0;
}
PrecomputePowers(n);
long long hash_A = HashEntireString(A, n);
vector<long long> prefix(m + 1, 0);
for (int i = 0; i < m; i++)
prefix[i + 1] = (prefix[i] * BASE + (B[i] - HASHER)) % MOD;
vector<int> positions;
for (int i = 0; i + n <= m; i++) {
long long current_hash = (prefix[i + n] - prefix[i] * powers[n]) % MOD;
if (current_hash < 0) current_hash += MOD;
if (current_hash == hash_A)
positions.push_back(i);
}
fout << positions.size() << "\n";
for (int i = 0; i < min((int)positions.size(), 1000); i++)
fout << positions[i] << " ";
fout << "\n";
return 0;
}