Cod sursa(job #1723608)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 1 iulie 2016 00:44:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <string>
#include <vector>

std::string A,B,aux;
std::vector<int> sol;

const int Nmax = 2000005;
int cnt;
int longest_p_s[Nmax];

void make_kmp_prefix(){
    int q = 0;
    for(int i = 2; i < A.length(); ++i){
        while(q && A[i] != A[q+1])
            q = longest_p_s[q];
        q += A[i] == A[q+1];
        longest_p_s[i] = q;
    }
}

void make_kmp_match(){
    int q = 0;
    for(int i = 1; i <= B.length(); ++i){
        while(q && B[i] != A[q+1])
            q = longest_p_s[q];
        q += B[i] == A[q+1];
        if(q + 1== A.length()){
            ++cnt;
            if(sol.size() < 1000)
                sol.push_back(i - A.length() + 1);
            q = longest_p_s[q];
        }
    }
}

int main()
{
    std::ifstream streamIn("strmatch.in");
    std::ofstream streamOut("strmatch.out");

    streamIn.sync_with_stdio(false);
    streamIn >> aux;
    A = "#" + aux;
    streamIn >> aux;
    B = "#" + aux;
    make_kmp_prefix();
    make_kmp_match();
    streamOut << cnt << "\n";
    for(int i = 0; i < sol.size(); ++i)
        streamOut << sol[i] << " ";

    return 0;
}