Cod sursa(job #2514881)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 27 decembrie 2019 11:12:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#define LMAX 2000005
#define SOLMAX 1005
using namespace std;

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

char a[LMAX], b[LMAX];
int p[LMAX];
int sol[SOLMAX], nr;
int m, n;

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

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

}

void afisprefix(){
    for(int i=1; i<=m; i++)
        g<<p[i]<<" ";

}

void afisSol(){
    g<<nr<<'\n';
    nr=min(nr, 1000);
    for(int i=1;i<=nr;i++)
        g<<sol[i]<<' ';
}
int main()
{
    f.getline(a+1, LMAX);
    f.getline(b+1, LMAX);
    m = strlen(a+1);
    n = strlen(b+1);
    formprefix();
    //afisprefix();
    cautCuvant();
    afisSol();
    return 0;
}