Pagini recente » Cod sursa (job #3319686) | Cod sursa (job #452528) | Cod sursa (job #1338076) | Cod sursa (job #2907853) | Cod sursa (job #3315029)
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 100;
const int BASE = 26;
const char HASHER = '0';
char A[NMAX], B[NMAX];
int HashEntireString(const char s[]) {
int hash = 0;
for (int i = 0; s[i]; i++) {
hash = hash * BASE + (s[i] - HASHER);
}
return hash;
}
int main() {
cin >> A >> B;
int n = strlen(A);
int m = strlen(B);
if (n > m) {
cout << 0;
return 0;
}
int hash_A = HashEntireString(A);
int current_hash = 0;
int power = 1;
for (int i = 0; i < n - 1; i++) power *= BASE;
for (int i = 0; i < n; i++) {
current_hash = current_hash * BASE + (B[i] - HASHER);
}
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 - (B[i - n] - HASHER) * power;
current_hash = current_hash * BASE + (B[i] - HASHER);
if (current_hash == hash_A) {
positions.push_back(i - n + 1);
cnt++;
}
}
cout << cnt << '\n';
for (int i = 0; i < min((int)positions.size(), 1000); i++) {
cout << positions[i] <<' ';
}
return 0;
}