Pagini recente » Cod sursa (job #1785975) | Cod sursa (job #134946) | Cod sursa (job #423663) | Diferente pentru problema/subsecvente intre reviziile 27 si 8 | Cod sursa (job #3315034)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1000005;
const int BASE = 26;
const char HASHER = '0';
const long long MOD = 1000000007;
char A[NMAX], B[NMAX];
int HashEntireString(const char s[]) {
int hash = 0;
for (int i = 0; s[i]; i++) {
hash = (1LL * hash * BASE + (s[i] - HASHER)) % MOD;
}
return hash;
}
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main() {
fin >> A >> B;
int n = strlen(A);
int m = strlen(B);
if (n > m) {
fout << 0;
return 0;
}
int hash_A = HashEntireString(A);
int current_hash = 0;
int power = 1;
for (int i = 0; i < n - 1; i++)
power = (1LL * power * BASE) % MOD;
// initial hash
for (int i = 0; i < n; i++) {
current_hash = (1LL * current_hash * BASE + (B[i] - HASHER)) % MOD;
}
int cnt = 0;
vector<int> positions;
if (current_hash == hash_A) {
cnt++;
positions.push_back(0);
}
for (int i = n; i < m; i++) {
current_hash = (current_hash - 1LL * (B[i - n] - HASHER) * power % MOD + MOD) % MOD;
current_hash = (1LL * current_hash * BASE + (B[i] - HASHER)) % MOD;
if (current_hash == hash_A) {
cnt++;
positions.push_back(i - n + 1);
}
}
fout << cnt << '\n';
for (int i = 0; i < min((int)positions.size(), 1000); i++) {
fout << positions[i] << ' ';
}
return 0;
}