Cod sursa(job #1315925)

Utilizator simaghitaSima Gheorghe Eugen simaghita Data 13 ianuarie 2015 12:29:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include<fstream>
#include<cstring>
#define mod1 100007
#define mod2 100021
using namespace std;
char a[2000010],b[2000010];
int lga,lgb;
int sol[2000010];
void citire()
{
    ifstream fin("strmatch.in");
    fin>>a;
    fin>>b;
    fin.close();

    lga=strlen(a);
    lgb=strlen(b);
}
void solve()
{
    ofstream fout("strmatch.out");

    int base=26,base1,base2,code1,code2,i;
    base1=base2=1;
    code1=code2=0;

    if(lga > lgb)
    {
        fout<<"0\n";
    }
    else
    {
        for(i=0;i<lga;++i)
        {
            code1=(code1*base + a[i])%mod1;
            code2=(code2*base + a[i])%mod2;
            if(i!=0)
            {
                base1=(base1*base)%mod1;
                base2=(base2*base)%mod2;
            }
        }

        int codeb1=0,codeb2=0;

        for(i=0;i<lga;++i)
        {
            codeb1=(codeb1*base + b[i]) % mod1;
            codeb2=(codeb2*base + b[i]) % mod2;
        }
        int nr=0;

        if(code1==codeb1 && code2==codeb2)
        {
            sol[0]=1;
            ++nr;
        }

        for(i=lga;i<lgb;++i)
        {
            codeb1=((codeb1-(b[i-lga]*base1)%mod1 + mod1)*base + b[i])%mod1;
            codeb2=((codeb2-(b[i-lga]*base2)%mod2 + mod2)*base+ b[i]) % mod2;

            if(code1==codeb1 && code2==codeb2)
            {
                sol[i- lga + 1]=1;
                ++nr;
            }
        }

        fout<<nr<<"\n";

        nr=0;
        for(i=0;i<lgb && nr<1000 ; ++i)
            if(sol[i]==1)
            {
                nr++;
                fout<<i<<" ";
            }
    }
    fout.close();

}

int main()
{
    citire();
    solve();
    return 0;
}