Cod sursa(job #1697802)

Utilizator serban_andreiserban andrei-catalin serban_andrei Data 2 mai 2016 22:25:32
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define maxim 2000010
#define baza 71

using namespace std;

int l1,l2,lim,ap;

vector <int> poz;

char a[maxim],b[maxim];

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

unsigned 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");

    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;

}