Cod sursa(job #1702314)

Utilizator serban_andreiserban andrei-catalin serban_andrei Data 14 mai 2016 23:14:27
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

#define lmax 2000010
const unsigned int BAZA = 71;

#define f cin
#define g cout


vector<int>pozsir;

char A[lmax],B[lmax];



unsigned int  p[lmax],h[lmax],la,lb,hasha,ap,i,j;

int lim;


unsigned int hashinterval(int i,int j){

return h[i]-h[j+1]*p[j-i+1];

}

int main()
{

    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f>>(A+1);
    f>>(B+1);


    la=strlen(A+1);
    lb=strlen(B+1);
    lim=lb-la+1;
    p[0]=1;
    for(i=1;i<=lb;i++)
    {
        p[i]=p[i-1]*BAZA;


    }

    for(i=lb;i>=1;i--)
    {

        h[i]=h[i+1]*BAZA+B[i];

    }
    for(i=la;i>=1;i--)
    {

        hasha=hasha*BAZA+A[i];

    }


    for(i=1;i<=lim;i++)
    {


        if(hashinterval(i,i+la-1)==hasha)
        {
            ap++;
            if(ap<=1000)
                pozsir.push_back(i-1);

        }
    }
    g<<ap<<'\n';

    for(int i = 0 ;i < pozsir.size() ; ++i)
        g<<pozsir[i]<<" ";

    return 0;


}