Cod sursa(job #2684827)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 14 decembrie 2020 22:58:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define NMAX 2000002
using namespace std;

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

char a[NMAX], b[NMAX];
int p[NMAX], afis[NMAX];
int main()
{
    int n, m, i, j, nr_afis=0;
    fin.getline(a, NMAX); n=strlen(a);
    fin.getline(b, NMAX); m=strlen(b);
    j=0; p[1]=0;
    for(i=1; i<n; i++)
    {
        while(j!=0&&a[i]!=a[j])j=p[j-1];
        if(a[i]==a[j]) j++;
        p[i]=j;
    }
    //for(i=0; i<n; i++) cout<<p[i<<' ';
    j=0;
    for(i=0; i<m && nr_afis<1000; i++)
    {
        while(j!=0&&a[j]!=b[i])
        {
            j=p[j-1];
        }
        if(a[j]==b[i]) j++;
        if(j==n) //am gasit o pozitie
        {
            afis[++nr_afis]=i-n+1;
        }
    }
    fout<<nr_afis<<"\n";
    for(i=1; i<=nr_afis; i++) fout<<afis[i]<<' ';
}