Cod sursa(job #2243151)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 19 septembrie 2018 23:18:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 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 - 1];
        }
          
        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);
  
    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;
        }
  
        if (k == needle.size()) {
            ++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;
}