Cod sursa(job #2243137)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 19 septembrie 2018 22:52:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <assert.h>

using LL = long long;
using ULL = int long long;

const std::string _problemName = "strmatch";

namespace std {
std::ifstream fin(_problemName + ".in"); 
std::ofstream fout(_problemName + ".out"); 
}

#define cin fin
#define cout fout

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 = 0;
 
    std::vector<int> pi = buildAutomaton(needle);
 
    // for (auto i : pi) {
        // std::cerr << i << ' ';
    // }
    // std::cerr << '\n';

    int k = 0;
 
    for (int i = 0; i < haystack.size(); ++i) {
        while (k != 0 && needle[k] != haystack[i]) {
            k = pi[k - 1];
        }
 
        if (needle[k] == haystack[i]) {
            ++k;
        }
 
        // std::cerr << "i = " << i << ' ' << "k = " << k << '\n';

        if (k == needle.size()) {

            // std::cerr << i << ' ';
            // std::cerr << haystack.substr(i - k + 1, i + 1) << '\n';

            ++matchesCount;
 
            if (firstMatches.size() < limit) {
                firstMatches.push_back(i - k + 1);
            }
 
            k = pi[k - 1];
        }
    }
 
    return std::make_pair(firstMatches, matchesCount);
}

int main() {
    std::string needle, haystack;
     
    std::cin >> needle >> haystack;
 
    auto ans = computeMatches(needle, haystack);
 
    std::cout << ans.second << '\n';
    for (auto i : ans.first) {
        std::cout << i << ' ';
    }
    std::cout << '\n';



    return 0;
}