Cod sursa(job #1932077)

Utilizator darian2001Clodnischi Darian Antonio darian2001 Data 19 martie 2017 15:29:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

long n,m,incadrari=0,gasit,i,j;
string sir1,sir2;
vector <int> pozitii(1000);
vector <int> sufix(2000000,0);

void calcul_prefix()
{
    j=0;
    for(i=1;i<n;i++)
    {
        while(j>0&&sir1[i]!=sir1[j])
            j=sufix[j];
        if(sir1[i]==sir1[j])
        {
            sufix[i]=j+1;
            j++;
        }

    }
}

void gasire_sir()
{
    i=0;
    for( j=0;j<m;j++)
    {
        while(i>0&&sir1[i]!=sir2[j])
            i=sufix[i-1];
        if(sir1[i]==sir2[j])
            i++;
        if(i==n)
        {
            if(incadrari<1000)
                pozitii[incadrari]=j-i+1;
            incadrari++;

        }
    }
}

void KMP()
{
     i=1,j=0;
    calcul_prefix();
    gasire_sir();
    g<<incadrari<<"\n";
    for(i=0;i<incadrari&&i<1000;i++)
        g<<pozitii[i]<<" ";
}


int main()
{
    f>>sir1>>sir2;
    n=sir1.size();
    m=sir2.size();
    KMP();
    f.close();g.close();
}