Cod sursa(job #1321485)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 19 ianuarie 2015 10:47:47
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>
#include <fstream>
#include <cstring>
#define p 73
#define nmax 2000005
#define mod1 100007
#define mod2 100023
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[nmax],b[nmax];
int h1[nmax],h2[nmax];
int ha1,ha2;
int n,m,c1,c2;
int match[2005],nr;

void Hashing()
{
    int i;
    c1=1;c2=1;
    for (i=0;i<n;i++)
                c1=(c1*p)%mod1;
    for (i=0;i<n;i++)
                c2=(c2*p)%mod2;

    h1[0]=b[0]-'A';h2[0]=b[0]-'A';
    //primul hashing
    for (i=1;i<n;i++)
                h1[i]=(h1[i-1]*p+ (b[i]-'A') )%mod1;
    for (i=n;i<=m;i++)
                h1[i]=(h1[i-1]*p+ (b[i]-'A')-(b[i-n]-'A')*c1 )%mod1;
    //al doilea hashing
    for (i=1;i<n;i++)
                h2[i]=(h2[i-1]*p+ (b[i]-'A') )%mod2;
    for (i=n;i<=m;i++)
                h2[i]=(h2[i-1]*p+ (b[i]-'A')-(b[i-n]-'A')*c2 )%mod2;

    for (i=0;i<n;i++)
                ha1=(ha1*p+(a[i]-'A')) %mod1;
    for (i=0;i<n;i++)
                ha2=(ha2*p+(a[i]-'A')) %mod2;

    for (i=0;i<m;i++)
        if (h1[i]==ha1&&h2[i]==ha2) {
                    nr++;
                    if (nr<=1000) match[nr]=i;
        }
}


int main()
{
    int i,j;
    f.getline(a,nmax);
    n=strlen(a);
    f.getline(b,nmax);
    m=strlen(b);

    Hashing();
    g<<nr<<'\n';
    if (nr<=1000)
            for (i=1;i<=nr;i++) g<<match[i]-n+1<<' ';
       else
            for (i=1;i<=1000;i++) g<<match[i]-n+1<<' ';


    return 0;
}