Cod sursa(job #2405726)

Utilizator minculescualex9Minculescu Alex minculescualex9 Data 14 aprilie 2019 19:59:06
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

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

#define minim(a, b) ((a < b) ? a : b)
#define sirMax 2000001

int lungimeA, lungimeB;
char sirA[sirMax], sirB[sirMax];
int pi[sirMax], pos[1024];

void make_prefix(){ //Calcul functie prefix
    int i, q = 0;

    pi[1] = 0;
    for(i = 2; i <= lungimeA; ++i){
        while(q > 0 && sirA[q+1] != sirA[i])
            q = pi[q];

        if(sirA[q+1] == sirA[i])
            ++q;

        pi[i] = q;
    }
}

void KMP(int &nr){  //Algoritm potrivire KMP
    int q = 0;
    nr = 0;

    for(int i = 1; i <= lungimeB; ++i){
        while(q > 0 && sirA[q+1] != sirB[i])
            q = pi[q];

        if(sirA[q+1] == sirB[i])
            ++q;

        if(q == lungimeA){
            q = pi[lungimeA];
            ++nr;

            if(nr <= 1000)
                pos[nr] = i - lungimeA;
        }
    }
}

int main()
{

            //Citire
    sirA[0] = ' ';
    sirB[0] = ' ';

//    fin.get(sirA + 1, sirMax);
//    fin.get();
//    fin.get(sirB + 1, sirMax);
    fin.getline(sirA + 1, sirMax);
    fin.getline(sirB + 1, sirMax);

    lungimeA = strlen(sirA) - 1;
    lungimeB = strlen(sirB) - 1;


            //Rezolvare problema
    int nr = 0; //Numarul de aparitii ale sirului A in sirul B;
    make_prefix();
    KMP(nr);

            //Afisare
    fout << nr << "\n";
    for(int i = 1; i <= minim(nr, 1000); ++i)
        fout << pos[i] << " ";


    fin.close();
    fout.close();
    return 0;
}