Cod sursa(job #1931976)

Utilizator darian2001Clodnischi Darian Antonio darian2001 Data 19 martie 2017 15:12:00
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

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

void calcul_prefix(int &i,int &j)
{
    if(sir1[i]==sir1[j])
    {
        sufix[i]=j+1;
        i++;j++;
    }
    else
    {
        if(j!=0)
        j=sufix[j-1];
        else
        {
            sufix[i]=0;
            i++;
        }
    }
    if(i<n)
        calcul_prefix(i,j);
}

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

void KMP()
{
    int i=1,j=0;
    calcul_prefix(i,j);
    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();
}