Cod sursa(job #1339359)

Utilizator addy01adrian dumitrache addy01 Data 10 februarie 2015 20:49:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

#define MAXN 2000001

#define P 73
#define MOD1 100007
#define MOD2 100021

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

char A[MAXN],B[MAXN];
bool match[MAXN];
int nr;

int main()
{
    int NA,NB,i,hashA1=0,hash1=0,hashA2=0,hash2=0;
    in.getline(A,MAXN);
    in.getline(B,MAXN);

    NA=strlen(A);
    NB=strlen(B);

    if(NA>NB)
    {
        out<<"0\n";
        return 0;
    }
    int P1=1;
    int P2=1;
    for(i=0;i<NA;i++)
    {
        hashA1=(hashA1*P+A[i])%MOD1;
        hashA2=(hashA2*P+A[i])%MOD2;

        if(i!=0)
            {
                P1=(P1*P)%MOD1;
                P2=(P2*P)%MOD2;
            }

    }

    for(i=0;i<NA;i++)
    {
        hash1=(hash1*P+B[i])%MOD1;
        hash2=(hash2*P+B[i])%MOD2;
    }
    if(hashA1==hash1&&hashA2==hash2)
        match[0]=1,nr++;

    for(i=NA;i<NB;i++)
    {
        hash1=((hash1-(B[i-NA]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
        hash2=((hash2-(B[i-NA]*P2)%MOD2+MOD2)*P+B[i])%MOD2;


        if(hashA1==hash1&&hashA2==hash2)
            match[i-NA+1]=1,nr++;
    }
    out<<nr<<"\n";
    nr=0;
    for(i=0;i<NB&&nr<1000;i++)
        if(match[i])
            {
                nr++;
                out<<i<<" ";
                }
    return 0;
}