Cod sursa(job #785316)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 8 septembrie 2012 13:42:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#define MOD1 100007
#define MOD2 100021
#define SG 73
#define NM 2000010

using namespace std;

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

string A,B;


int N,M,i,j;
int HASH1,HASH2,HASHC1,HASHC2;
int P1,P2;
int MATCH[NM];

int main ()
{
    getline(f,A);
    getline(f,B);

    N=A.size();
    M=B.size();

    P1=P2=1;

    for (i=0; i<N; i++)
    {
        HASH1=(HASH1*SG+A[i])%MOD1;
        HASH2=(HASH2*SG+A[i])%MOD2;

        if (i>0)
        {
            P1=(P1*SG)%MOD1;
            P2=(P2*SG)%MOD2;
        }
    }

    for (i=0; i<M; i++)
    {
        if (i>=N)
        {
            HASHC1=(HASHC1-(B[i-N]*P1)%MOD1+MOD1)%MOD1;
            HASHC2=(HASHC2-(B[i-N]*P2)%MOD2+MOD2)%MOD2;
        }
        HASHC1=(HASHC1*SG+B[i])%MOD1;
        HASHC2=(HASHC2*SG+B[i])%MOD2;

        if (HASHC1==HASH1 && HASHC2==HASH2)
            MATCH[++MATCH[0]]=i-N+1;
    }

    g << min(MATCH[0],1000) << '\n';
    for (i=1; i<=min(MATCH[0],1000); i++)
        g << MATCH[i] << ' ';

    g << '\n';
    f.close();
    g.close();
    return 0;
}