Cod sursa(job #2480828)

Utilizator cristina-criCristina cristina-cri Data 26 octombrie 2019 10:33:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <iostream>
#include <cstring>
#define lungimeMax 2000005
using namespace std;

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

char a[lungimeMax], b[lungimeMax];
int p[lungimeMax], n, m, poz[1005], nr;

void formPref()
{
    int pi = 0;
    for(int i = 2; i <= n; i++)
    {
        while(pi > 0 && a[i] != a[pi+1])
            pi = p[pi];
        if(a[i] == a[pi+1])
            ++pi;
        p[i]=pi;
    }
}

void afis()
{
    for(int i=0; i<=n; i++)
        cout<<p[i]<<' ';
}

void matching()
{
    int pi = 0;
    for(int i = 1; i <= m; i++)
    {
        while(pi > 0 && b[i] != a[pi+1])
            pi = p[pi];
        if(b[i] == a[pi+1])
            ++pi;
        if(pi == n)
        {
            nr++;
            if(nr <= 1000)
                poz[nr]=i-n;
        }
    }
}

int main()
{

    f.getline(a+1, lungimeMax);
    f.getline(b+1, lungimeMax);
    //cout<<a+1<<'\n'<<b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    formPref();
    //afis();
    matching();
    g<<nr<<'\n';
    for(int i = 1; i <= nr; i++)
        g<<poz[i]<<' ';
    return 0;
}