Cod sursa(job #2480856)

Utilizator dragos03dragos popescu septimiu dragos03 Data 26 octombrie 2019 10:42:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001],b[2000001];
int ap[2000001],n,m,cont,sirsol[2000001];

void citire()
{
    f.get(a+1,2000001);
    f.get();
    f.get(b+1,2000001);
    //a[0]='*';
    //b[0]='*';

}

void gensufx()
{
    int k=0;
    for(int i=2;i<=n;i++)
    {

            while(k!=0&&a[i]!=a[k+1])
            k=ap[k];

            if(a[i]==a[k+1])
                k++;

            ap[i]=k;

    }
}

void KMP()
{
    int k=0;
    for(int i=1;i<=m;i++)
    {
        while(k>0&&b[i]!=a[k+1])
            k=ap[k];
        if(b[i]==a[k+1])
            k++;
        if(k==n)
            sirsol[++cont]=i-k;
    }


}

void afis()
{
    g<<cont;
    g<<'\n';
    for(int i=1;i<=cont;i++)
{
        if(i%1000==0)
        g<<'\n';
        g<<sirsol[i]<<' ';
}
}

int main()
{citire();
n=strlen(a+1);
m=strlen(b+1);
gensufx();
KMP();
//cout<<a<<'\n'<<b;
afis();



    return 0;
}