Cod sursa(job #2675042)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 21 noiembrie 2020 09:37:08
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;

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

int p[NMAX];
char a[NMAX], b[NMAX];
int sol[1005];

void citire(){
    f.getline(a+1, NMAX);
    f.getline(b+1, NMAX);
}

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

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

void afisare(int nr){
    g<<nr<<'\n';
    nr = min(nr, 1000);
    for(int i=1; i<=nr; i++)
        g<<sol[i]<<' ';
}
int main()
{
    citire();
    form_prefix();
    int nr = match_strings();
    afisare(nr);
    return 0;
}