Pagini recente » Cod sursa (job #1784232) | Cod sursa (job #192100) | Cod sursa (job #2029367) | Cod sursa (job #213760) | Cod sursa (job #2072145)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
unsigned long long GetTimeStamp() {
unsigned a, b;
asm("rdtsc;\n\t" : "=d"(a), "=a"(b));
return (unsigned long long)a << 32 | b;
}
unsigned RandInt() {
static unsigned x = 123456789, y = 362436069,
z = (unsigned)(GetTimeStamp() >> 32), w = (unsigned)GetTimeStamp();
unsigned t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
class RollingHashFactory {
public:
explicit RollingHashFactory(int num_mods, int mx_size) : mod_(num_mods), base_(num_mods), base_powers_(num_mods, vector<int>(mx_size + 1)) {
for (int i = 0; i < num_mods; i += 1) {
mod_[i] = SearchPrime(RandInt() % 500000000 + 500000000);
base_[i] = SearchPrime(RandInt() % 10000 + 30);
base_powers_[i][0] = 1;
for (int j = 1; j <= mx_size; j += 1) {
base_powers_[i][j] = (long long)base_powers_[i][j - 1] * base_[i] % mod_[i];
}
}
}
size_t size() const {
return mod_.size();
}
int base(const int idx) const {
return base_[idx];
}
int mod(const int idx) const {
return mod_[idx];
}
int base_exponent(const int idx, const int power) const {
return base_powers_[idx][power];
}
private:
explicit RollingHashFactory();
RollingHashFactory(const RollingHashFactory& other) = delete;
static int SearchPrime(int start_point) {
while (not IsPrime(start_point)) {
start_point += 1;
}
return start_point;
}
static bool IsPrime(const int number) {
if (number % 2 == 0) {
return number == 2;
}
for (int i = 3; i * i <= number; i += 2) {
if (number % i == 0) {
return false;
}
}
return true;
}
vector<int> mod_, base_;
vector<vector<int>> base_powers_;
};
class RollingHashState {
public:
explicit RollingHashState(const RollingHashFactory* factory) : factory_ptr_(factory), hashes_(factory->size()), length_(0) { }
RollingHashState& operator +=(const int value) {
for (size_t i = 0; i < hashes_.size(); i += 1) {
hashes_[i] = ((long long)hashes_[i] * factory_ptr_->base(i) + value) % factory_ptr_->mod(i);
}
length_ += 1;
return *this;
}
RollingHashState& operator +=(const RollingHashState& rhs) {
for (size_t i = 0; i < hashes_.size(); i += 1) {
hashes_[i] = ((long long)hashes_[i] * factory_ptr_->base_exponent(i, rhs.length_) + rhs.hashes_[i]) % factory_ptr_->mod(i);
}
length_ += rhs.length_;
return *this;
}
RollingHashState& operator -=(const RollingHashState& prefix) {
for (size_t i = 0; i < hashes_.size(); i += 1) {
hashes_[i] = (hashes_[i] - (long long)prefix.hashes_[i] * factory_ptr_->base_exponent(i, length_ - prefix.length_)) % factory_ptr_->mod(i);
if (hashes_[i] < 0) {
hashes_[i] += factory_ptr_->mod(i);
}
}
length_ -= prefix.length_;
return *this;
}
friend RollingHashState operator +(const RollingHashState& lhs, const RollingHashState& rhs) {
return RollingHashState(lhs) += rhs;
}
friend RollingHashState operator +(const int value, const RollingHashState& rhs) {
RollingHashState base(rhs.factory_ptr_);
base += value; base += rhs;
return base;
}
friend RollingHashState operator +(const RollingHashState& lhs, const int value) {
return RollingHashState(lhs) += value;
}
friend RollingHashState operator -(const RollingHashState& lhs, const RollingHashState& rhs) {
return RollingHashState(lhs) -= rhs;
}
bool operator ==(const RollingHashState& rhs) const {
return length_ == rhs.length_ and hashes_ == rhs.hashes_;
}
private:
explicit RollingHashState();
const RollingHashFactory* const factory_ptr_;
vector<int> hashes_;
int length_;
};
class SubstringHashes {
public:
template<class Iter>
SubstringHashes(Iter from, Iter to) {
RollingHashState st(factory_ptr_);
while (from != to) {
st += *from;
prefix_hashes_.push_back(st);
from++;
}
}
RollingHashState Query(int li, int lf) const {
RollingHashState ans = prefix_hashes_[lf];
if (li > 0) {
ans -= prefix_hashes_[li - 1];
}
return ans;
}
private:
vector<RollingHashState> prefix_hashes_;
static const RollingHashFactory* const factory_ptr_;
};
constexpr int kMaxLen = 1000000;
RollingHashFactory factory(1, kMaxLen);
const RollingHashFactory* const SubstringHashes::factory_ptr_ = &factory;
int main() {
#ifdef INFOARENA
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#endif
string a, b; cin >> a >> b;
RollingHashState rhs_a(&factory);
for (auto&& ch : a) {
rhs_a += ch;
}
SubstringHashes shb(b.begin(), b.end());
vector<size_t> positions;
int num_matches = 0;
for (size_t i = 0; i + a.size() - 1 < b.size(); i += 1) {
if (shb.Query(i, i + a.size() - 1) == rhs_a) {
num_matches += 1;
if (num_matches <= 1000) {
positions.push_back(i);
}
}
}
cout << num_matches << endl;
for (auto&& match : positions) {
cout << match << ' ';
}
cout << '\n';
}