Cod sursa(job #1407048)

Utilizator thecoreUPB-Catana-Oprea-Poenaru thecore Data 29 martie 2015 18:00:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <cstring>
#define Nmax 2000003
#define wmax  1000
using namespace std;
char subsir[Nmax], sir[Nmax];
int pi[Nmax], poz[Nmax];
int n, m, nr = 0;
int i, j;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.getline(subsir, Nmax);
    f.getline(sir, Nmax);
    n = strlen(subsir);
    m = strlen(sir);
    pi[0]=pi[1]=0;
    for (i=1,j=0; i<n; i++)
    {
        while (j>0 && subsir[i]!=subsir[j])j=pi[j];
        if (subsir[i]==subsir[j])j++;
        pi[i+1]=j;
    }
    for (i=j=0; i<m; i++)
    {
        while (j>0 && subsir[j]!=sir[i]) j=pi[j];
        if (subsir[j]==sir[i]) j++;
        if (j==n)
        {
            if (nr<wmax) poz[nr]=i-n+1;
            nr++;
            j=pi[j];
        }
    }
    g<<nr<<"\n";
    if (nr>wmax) nr=wmax;
    for (i=0; i<nr; i++)
        g<<poz[i]<<" ";
    return 0;
}