Cod sursa(job #1809030)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 18 noiembrie 2016 16:27:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

class KMP {
    public:
        KMP(const string& text) : text_(text) {}

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

            vector<int> pi(pattern.size(), 0);
            BuildPi(pattern, pi);

            int q = 0;
            for (int i = 0; i < (int)text_.size(); i++) {
                while (q && pattern[q] != text_[i]) {
                    q = pi[q - 1];
                }

                if (pattern[q] == text_[i]) {
                    q++;
                }

                if (q == (int)pattern.size()) {
                    if (++count <= max_index_count) {
                        indexes.push_back(i - pattern.size() + 1);
                    }
                }
            }

            return {count, indexes};
        }

    private:
        string text_;

        void BuildPi(const string& pattern, vector<int>& pi) {
            int q = 0;
            for (int i = 1; i < (int)pattern.size(); i++) {
                while (q && pattern[q] != pattern[i]) {
                    q = pi[q - 1];
                }

                if (pattern[q] == pattern[i]) {
                    q++;
                }

                pi[i] = q;
            }
        }
};

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

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

    string pattern;
    cin >> pattern;

    string text;
    cin >> text;

    KMP kmp(text);

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

    return 0;
}