Cod sursa(job #1423842)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 22 aprilie 2015 20:32:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <string>
#include <vector>
#include <iostream>
#include <cstring>
#define NMAX 2000010

using namespace std;

vector<int> sol;
char A[NMAX], B[NMAX];
int nrSol=0, lgA, lgB, urm[NMAX];

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

void construiesteFunctiaEsec()
{
    int i, j=0;

    for (i=2; i<=lgA; ++i)
    {
        while (j>0 && A[j+1]!=A[i])
        {
            j=urm[j];
        }

        if (A[j+1]==A[i]) ++j;

        urm[i]=j;
    }

    //for (i=1; i<=lgA; ++i) cout<<urm[i]<<" ";
}

void potrivireaSirurilor()
{
    int j=0, i;

    for (i=1; i<=lgB; ++i)
    {
        while (j>0 && A[j+1]!=B[i])
        {
            j=urm[j];
        }

        if (A[j+1]==B[i]) ++j;

        if (j==lgA)
        {
            j=urm[j];
            ++nrSol;
            if (sol.size()<1000) sol.push_back(i-lgA);
        }
    }
}


int main()
{
    f.getline(A+1, NMAX);
    f.getline(B+1, NMAX);
    lgA=strlen(A+1); lgB=strlen(B+1);

    construiesteFunctiaEsec();

    potrivireaSirurilor();

    g<<nrSol<<"\n";
    for (int i=0; i<sol.size(); ++i)
        g<<sol[i]<<" ";

    f.close();
    g.close();
    return 0;
}