Cod sursa(job #2072145)

Utilizator mlc_oficialBoris Barca mlc_oficial Data 21 noiembrie 2017 14:45:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 5.48 kb
#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';
}