Cod sursa(job #2243150)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 19 septembrie 2018 23:17:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <assert.h>
#include <cstring>

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

const int LMAX = 2000005;

char needle[LMAX];
char haystack[LMAX];

int needleSize;
int haystackSize;

std::vector<int> buildAutomaton() {
    std::vector<int> pi(needleSize);
 
    pi[0] = 0;
 
    int k = 0;
    for (int i = 1; i < needleSize; ++i) {
        // int k = pi[i - 1];
         
        while (k != 0 && needle[i] != needle[k]) {
            k = pi[k - 1];
        }
         
        if (needle[i] == needle[k]) {
            ++k;
        }
        pi[i] = k;
    }
 
    return pi;
}


std::pair< std::vector<int>, int> computeMatches(const int limit = 1000) {
    std::vector<int> firstMatches;
    firstMatches.reserve(limit);

    int matchesCount = 0;
 
    std::vector<int> pi = buildAutomaton();
 
    // for (auto i : pi) {
        // std::cerr << i << ' ';
    // }
    // std::cerr << '\n';

    int k = 0;
 
    for (int i = 0; i < haystackSize; ++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 == needleSize) {

            // 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::cin.getline(needle, LMAX);
    std::cin.getline(haystack, LMAX);

    needleSize = strlen(needle);
    haystackSize = strlen(haystack);

    auto ans = computeMatches();
 
    std::cout << ans.second << '\n';
    for (auto i : ans.first) {
        std::cout << i << ' ';
    }
    std::cout << '\n';



    return 0;
}