Cod sursa(job #1675138)

Utilizator EberardoVladianu Cosmin Eberardo Data 5 aprilie 2016 09:30:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int m,n,nr;
char a[2000001],b[2000001];
int pi[2000001],contor;
queue<int> coada;
void citire()
{
    fin.get(a,2000001);
    fin.get();
    fin.get(b,2000001);
    m=strlen(b);
    n=strlen(a);
}

void calcul_prefixe()
{
    int k,i;
    k=0;
    pi[1]=0;
    for(i=2;i<=n;i++)
    {
        while(k>0 and (a[k]!=a[i-1]))
            k=pi[k];
        if(a[k]==a[i-1])
            k++;
        pi[i]=k;
    }
}

void potrivire()
{
    int i,q=0;;

    for(i=1;i<=m;i++)
    {
        while(q>0 and (a[q]!=b[i-1]))
            q=pi[q];
        if(a[q]==b[i-1])
            q++;
        if(q==n)
        {
            contor++;
            if(contor<=1000)
                coada.push(i-n);
        }

    }
}

void afisare()
{
    int maxi,x;
    fout<<contor<<'\n';
    while(!coada.empty())
    {
        x=coada.front();
        fout<<x<<' ';
        coada.pop();
    }
}

int main()
{
    citire();
    calcul_prefixe();
    potrivire();
    afisare();
    return 0;
}