Cod sursa(job #1675600)

Utilizator malina_floreaMalina Florea malina_florea Data 5 aprilie 2016 13:46:31
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#define DMAX 2000010
#define MAX 1000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

void citire();
void rez();
void afisare();
inline int minim(int, int);

int m, n;
char sir1[DMAX], sir2[DMAX];

int prec[DMAX];

int nrsol, sol[MAX+10];

int main()
{
    citire();
    rez();
    afisare();
    
    fin.close();
    fout.close();
    return 0;
}

void citire()
{
    fin.getline(sir2+1, DMAX);
    m=(int)strlen(sir2+1);
    
    fin.getline(sir1+1, DMAX);
    n=(int)strlen(sir1+1);
}

void rez()
{
    int a, b, i, x;
    
    //prima parte
    
    prec[1]=0;
    a=0;
    for (b=2; b<=m; b++)
    {
        while (a>0 && sir2[a+1]!=sir2[b])
            a=prec[a];
        
        if (sir2[a+1]==sir2[b])
            a=a+1;
        
        prec[b]=a;
    }
    
    //a doua parte
    
    x=0;
    for (i=1; i<=n; i++)
    {
        while (x>1 && sir2[x+1]!=sir1[i])
            x=prec[x];
        
        if (sir2[x+1]==sir1[i]) x++;
        
        if (x==m)
        {
            nrsol++;
            if (nrsol<=MAX) sol[nrsol]=i-m+1;
            //fout<< i-m+1<< '\n';
            x=prec[x];
        }
    }
}

void afisare()
{
    int i, x=minim(nrsol, MAX);
    fout<< nrsol<< '\n';
    for (i=1; i<=x; i++)
        fout<< sol[i]-1<< ' ';
}

inline int minim(int a, int b)
{
    if (a<b) return a;
    return b;
}