Cod sursa(job #1617746)

Utilizator andreiudilaUdila Andrei andreiudila Data 27 februarie 2016 16:09:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cstring>
#include <fstream>
#include <iostream>

#define P 73
#define mod1 100007
#define mod2 100021

using namespace std;

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

string a, b, s;
int na, nb,n,nr,i;
int z[4000005];
int l,r;

int main()
{

    getline(fin, a);
    getline(fin, b);

    s=a+'#'+b;

    n=s.length();

    for(i=1;i<n;++i)
    {
        if(i>r)
        {
            int p1=i;
            int p2=0;

            while(s[p1]==s[p2])
            {
                ++p1; ++p2;
                ++z[i];
            }

            r=p1-1;
            l=i;
        }

        else{

        if(z[i-l]<r-i+1) z[i]=z[i-l];

        else {

        int p1=r+1;
        int p2=r-i+1;

        z[i]=r-i+1;
        while(s[p1]==s[p2])
        {

            ++p1;
            ++p2;
            ++z[i];
        }

            r=p1-1;
            l=i;

        }

        }

        if(z[i]==a.length()) ++nr;
    }

        fout<<nr<<'\n';

        nr=0;

        int k=a.length()+1;
        int k2=s.length();
        int k3=a.length();

         while(k<k2 && nr<1000)
        {

            if(z[k]==k3)
            {
              fout<<k-a.length()-1<<" ";
              nr++;
            }


            ++k;


        }




    return 0;
}