Cod sursa(job #1697809)

Utilizator serban_andreiserban andrei-catalin serban_andrei Data 2 mai 2016 22:41:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define maxim 2000010
#define baza 73

using namespace std;


vector <int> poz;

char a[maxim],b[maxim];

unsigned int h[maxim],p[maxim];

unsigned int intr(int i,int j)
{
    return h[i]-h[j+1]*p[j-i+1];
}


int main ()
{

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

    unsigned hasha=0;
    int l1,l2,lim,ap=0,i;

    f>>(a+1);

    f>>(b+1);

    l1=strlen(a+1);

    l2=strlen (b+1);

    p[0]=1;

    for(i=1;i<=l2;++i)
    {
        p[i]=p[i-1]*baza;
    }

    for(i=l2;i>=1;i--)
    {
        h[i]=h[i+1]*baza+b[i];
    }
    for(i=l1;i>=1;i--)
    {
        hasha=hasha*baza+a[i];
    }

    lim=l2-l1+1;
    for(i=1;i<=lim;i++)
    {
        if(intr(i,i+l1-1)==hasha)
        {
            ++ap;
            if(ap<=1000)
                poz.push_back (i-1);
        }
    }
    g<<ap<<'\n';
    for(auto x:poz)
        g<<x<<' ';
    return 0;

}