Cod sursa(job #1867500)

Utilizator asavu16Andrei Savu asavu16 Data 4 februarie 2017 10:17:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define MOD1 666013
#define MOD2 10003
int h1,h2,m,n,i,sol[10004],s,nr,v1,v2,p1,p2;
char a[2000012],b[2000012];
int main()
{
    f.getline(a,2000012);
    f.getline(b,2000012);
    m=strlen(a);
    n=strlen(b);
    p1=1;
    p2=1;
    for(i=0; i<m; ++i)
    {
        h1=(h1*101%MOD1+(int)a[i])%MOD1;
        h2=(h2*109%MOD2+(int)a[i])%MOD2;
        v1=(v1*101%MOD1+(int)b[i])%MOD1;
        v2=(v2*109%MOD2+(int)b[i])%MOD2;


        if (i>0)
        {
            p1*=101;
            p1%=MOD1;
            p2*=109;
            p2%=MOD2;
        }
    }
    if (v1==h1 && v2==h2)
    {
        nr++;
        sol[++s]=i-m;
    }
    for (i=m; i<n; i++)

    {
        // v1 = ((((v1 - (int)b[i-m]*p1)*101)% MOD1 + MOD1)*101 + (int)b[i])%MOD1;
        // v2 = ((((v2 - (int)b[i-m]*p2)*109)% MOD2 + MOD2)*109 + (int)b[i])%MOD2;
        v1 = (( v1-( int (b[i-m])*p1 ) % MOD1 + MOD1) * 101 + int(b[i])) % MOD1;
        v2 = (( v2- (int (b[i-m])*p2 ) % MOD2 + MOD2) * 109 + int(b[i])) % MOD2;
        if (v1==h1 && v2==h2)
        {
            nr++;
            if(nr<=1000)
            sol[++s]=i-m+1;
        }

    }
    g<<nr<<'\n';
    for(i=1; i<=s; ++i)
        g<<sol[i]<<" ";

    return 0;
}