Pagini recente » Cod sursa (job #3363154) | Borderou de evaluare (job #3361363) | Cod sursa (job #3363203) | Cod sursa (job #3363145) | Cod sursa (job #3363205)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#ifdef LOCAL
#define fin cin
#define fout cout
#else
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#endif
const long long B=67;
const int MOD=1e9+7, NMAX=2e6;
long long hash_b[NMAX];
long long puteri_B[NMAX];
vector<int> rasp;
int my_hash(char ch, int poz) {
if (ch >= '0' && ch <= '9') return ((ch - '0' + 1) * puteri_B[poz]) % MOD;
if (ch >= 'a' && ch <= 'z') return ((ch - 'a' + 11) * puteri_B[poz]) % MOD;
return ((ch - 'A' + 37) * puteri_B[poz]) % MOD;
}
long long fastpow(int x, int y) {
if (y == 0) return 1;
long long jum = fastpow(x, y / 2);
if (y % 2 == 0) return (jum * jum) % MOD;
return (((jum * jum) % MOD) * x) % MOD;
}
int main() {
string a, b;
int n=0;
long long hash_a=0;
fin >> a >> b;
puteri_B[0] = 1;
for (int i=1; i<NMAX; i++) puteri_B[i] = (puteri_B[i - 1] * B) % MOD;
for (int i=0; i<a.size(); i++) {
hash_a = (hash_a + my_hash(a[i], i)) % MOD;
}
hash_b[0] = my_hash(b[0], 0);
for (int i=1; i<b.size(); i++)
hash_b[i] = (hash_b[i - 1] + my_hash(b[i], i)) % MOD;
if (hash_b[a.size() - 1] == hash_a) {
n++;
rasp.push_back(0);
}
for (int i=0; i<b.size()-a.size(); i++)
if ((((hash_b[i + a.size()] - hash_b[i] + MOD) % MOD) * fastpow(puteri_B[i + 1], MOD - 2)) % MOD == hash_a) {
n++;
if (n <= 1000) rasp.push_back(i + 1);
}
fout << n << '\n';
for (auto poz:rasp) fout << poz << ' ';
}