Cod sursa(job #2031721)

Utilizator bucuralexandraioana05Bucur Alexandra bucuralexandraioana05 Data 3 octombrie 2017 18:44:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <string.h>
#include <fstream>

using namespace std;

ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int S[2000010];
char N[2000010];
int n;
char H[2000010];
int h;
int k,f,nrap, nrsolutii[1001], cont;

int main()
{
    fi>>N+1;
    n=strlen(N+1);
    fi>>H;
    h=strlen(H);
    /// se construieste sirul S
    S[0]=-1;
    S[1]=0;
    for (int i=2; i<=n; i++)
    {
        /// se obtine S[i]
        k=i-1;
        while (S[k]!=-1 && N[S[k]+1]!=N[i])
            k=S[k];
        if (S[k]==-1)
            S[i]=0;
        else
            S[i]=S[k]+1;
    }
    nrap=0;
    f=0;
    cont=0;
    for (int i=0; i<h; i++)
    {
        /// se cauta cel mai din dreapta lemming ce supravietuieste literei H[i]
        while (f!=-1)
        {
            if (H[i]==N[f+1])
                break;
            f=S[f];
        }
        if (f==-1)
            f=0;
        else
            f++;
        if (f==n)
        {
            nrap++;
            if (cont==1000)
                ;
            else
                ///nu trebuie scrie mai mult de 1000 solutii
                nrsolutii[++cont]=i-n+1;
            f=S[f];
        }
    }
    fo<<nrap<<"\n";
    for( int i=1; i<=cont; ++i)
        fo<<nrsolutii[i]<<" ";

    fi.close();
    fo.close();
    return 0;
}