Cod sursa(job #2242325)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 18 septembrie 2018 14:49:26
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <unordered_map>

using LL  = long long;
using ULL = unsigned long long;

std::vector<int> buildAutomaton(const std::string& s) {
    std::vector<int> pi(s.size());

    pi[0] = 0;

    for (int i = 1; i < s.size(); ++i) {
        int k = pi[i - 1];
        
        while (k != 0 && s[i] != s[k]) {
            k = pi[k];
        }
        
        if (s[i] == s[k]) {
            ++k;
        }
        pi[i] = k;
    }

    return pi;
}

std::pair< std::vector<int>, int> computeMatches(const std::string& needle, const std::string& haystack, const int limit = 1000) {
    std::vector<int> firstMatches;
    int matchesCount;

    std::vector<int> pi = buildAutomaton(needle);

    int k = 0;

    for (int i = 0; i < haystack.size(); ++i) {
        while (k != 0 && needle[k] != haystack[i]) {
            k = pi[k];
        }

        if (needle[k] == haystack[i]) {
            ++k;
        }

        if (k == needle.size()) {
            ++matchesCount;

            if (matches.size() < limit) {
                matches.push_back(i - k + 1);
            }

            k = pi[k - 1];
        }
    }

    return matches;
}

int main() {

    std::ifstream fin("strmatch.in");
    std::ofstream fout("strmatch.out");

    std::string needle, haystack;
    
    fin >> needle >> haystack;

    auto ans = computeMatches(needle, haystack);

    fout << ans.second << '\n';
    for (auto i : ans.first) {
        fout << i << ' ';
    }
    fout << '\n';

    return 0;
}