Cod sursa(job #1787553)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 24 octombrie 2016 19:52:22
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 4.82 kb
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

class RollingHash {
    public:
        RollingHash(const string& text) : text_(text) {
            was_preprocessed_ = false;
        }

        void Preprocess(int length, int max_index_count) {
            was_preprocessed_ = true;
            vector<pair<int, int>> codes = GetCodes(length);
            int current_index = 0;
            for (pair<int, int> code : codes) {
                AddIndex(code.first, code.second, current_index, max_index_count);
                current_index++;
            }
        }

        pair<int, vector<int>> GetMatchingIndexes(const string& pattern, int max_index_count) {
            int count = 0;
            vector<int> indexes;
            indexes.reserve(max_index_count);

            int match[2] = {0, 0};
            for (int i = 0; i < (int)pattern.size(); i++) {
                for (int j = 0; j < 2; j++) {
                    match[j] = (match[j] * kBase + pattern[i]) % kHashPrimes[j];
                }
            }

            if (was_preprocessed_) {
                long long pattern_code = GetCombinedCode(match[0], match[1]);
                return {count_[pattern_code], matchings_[pattern_code]};
            }

            int length = pattern.size();
            pair<int, int> pattern_code = {match[0], match[1]};

            int powered_base[2] = {1, 1};
            for (int i = 0; i < length - 1; i++) {
                for (int j = 0; j < 2; j++) {
                    powered_base[j] = (powered_base[j] * kBase) % kHashPrimes[j];
                }
            }

            match[0] = match[1] = 0;
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < 2; j++) {
                    match[j] = (match[j] * kBase + text_[i]) % kHashPrimes[j];
                }
            }
            return {count, indexes};

            if (make_pair(match[0], match[1]) == pattern_code) {
                count++;
                indexes.push_back(0);
            }

            for (int i = length; i < (int)text_.size(); i++) {
                for (int j = 0; j < 2; j++) {
                    match[j] = ((match[j] - (powered_base[j] * text_[i - length]) % kHashPrimes[j]
                                 + kHashPrimes[j]) * kBase + text_[i]) % kHashPrimes[j];
                }

                /* if (make_pair(match[0], match[1]) == pattern_code) { */
                /*     count++; */
                /*     if ((int)indexes.size() < max_index_count) { */
                /*         indexes.push_back(i - length + 1); */
                /*     } */
                /* } */
            }

            return {count, indexes};
        }

    private:
        const int kHashPrimes[2] = {100003, 666013};
        static const int kBase = 137;
        bool was_preprocessed_;
        string text_;
        unordered_map<long long, vector<int>> matchings_;
        unordered_map<long long, int> count_;

        long long GetCombinedCode(int x, int y) {
            return 1LL * x * kHashPrimes[1] + y;
        }

        void AddIndex(int match0, int match1, int index, int max_index_count) {
            long long combinedCode = GetCombinedCode(match0, match1);
            count_[combinedCode]++;
            if ((int)matchings_[combinedCode].size() < max_index_count) {
                matchings_[combinedCode].push_back(index);
            }
        }

        vector<pair<int, int>> GetCodes(int length) {
            vector<pair<int, int>> codes;

            int powered_base[2] = {1, 1};
            for (int i = 0; i < length - 1; i++) {
                for (int j = 0; j < 2; j++) {
                    powered_base[j] = (powered_base[j] * kBase) % kHashPrimes[j];
                }
            }

            int match[2] = {0, 0};
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < 2; j++) {
                    match[j] = (match[j] * kBase + text_[i]) % kHashPrimes[j];
                }
            }
            /* codes.push_back({match[0], match[1]}); */

            for (int i = length; i < (int)text_.size(); i++) {
                for (int j = 0; j < 2; j++) {
                    match[j] = ((match[j] - (powered_base[j] * text_[i - length]) % kHashPrimes[j]
                                 + kHashPrimes[j]) * kBase + text_[i]) % kHashPrimes[j];
                }
                codes.push_back({match[0], match[1]});
            }

        }
};

int main() {
    cin.sync_with_stdio(false);

    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");

    string pattern;
    cin >> pattern;

    string text;
    cin >> text;

    RollingHash hash(text);
    /* hash.Preprocess(pattern.size(), 1000); */

    pair<int, vector<int>> answer = hash.GetMatchingIndexes(pattern, 1000);
    cout << answer.first << '\n';
    for (int it : answer.second) {
        cout << it << " ";
    }

    return 0;
}