Cod sursa(job #2344851)

Utilizator AndreiGSGhiurtu Andrei AndreiGS Data 15 februarie 2019 18:03:45
Problema Potrivirea sirurilor Scor 96
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int ap[1001], k, matches;

void getZarr(string str, int Z[]);

void cautare(string text, string pattern)
{
    //concateneaza pat cu txt
    string concat=pattern+"$"+text;
    int l=concat.length();

    //construieste vectorul Z
    int Z[l];
    getZarr(concat, Z);

    //verificam match-urile
    for(int i=0; i<l; ++i)
    {
        //daca z[i] == lungimea pat am gasit un match
        if(Z[i]==pattern.length())
        {
            matches++;
            if(k<1000)
                ap[k++]=i-pattern.length()-1;
        }
    }
}

//Construieste Z
void getZarr(string str, int Z[])
{
    int n=str.length();
    int L, R, k;

    L=R=0;
    for(int i=1; i<n; ++i)
    {
        // if i>R nimic nu se "match-uieste"
        if(i>R)
        {
            L=R=i;
            while(R<n && str[R-L]==str[R])
                R++;
            Z[i]=R-L;
            R--;
        }
        else
        {
            k=i-L;
            if(Z[k]<R-i+1)
                Z[i]=Z[k];
            else
            {
                L=i;
                while(R<n && str[R-L]==str[R])
                    R++;
                Z[i]=R-L;
                R--;
            }
        }
    }
}

int main()
{
    string pat, text;
    getline(f, pat);
    getline(f, text);
    cautare(text, pat);
    if(matches)
    {
        g<<matches<<'\n';
        for(int i=0; i<k; ++i)
            g<<ap[i]<<' ';
        return 0;
    }
    else
        g<<'0';

    return 0;
}