Cod sursa(job #1328174)

Utilizator theprdvtheprdv theprdv Data 28 ianuarie 2015 05:49:22
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
// Rabin Karp (2 bases)
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;

fstream fin("strmatch.in", ios::in);
fstream fout("strmatch.out", ios::out);

#define MAX 2000005
#define MOD1 100007
#define MOD2 100021
#define base1 73

char A[MAX], B[MAX];
int NA, NB;
int hashA1, hashA2, P1, P2, sol[1001];

int main()
{
    int P1=1, P2=1;
    fin.getline(A, MAX);    NA=strlen(A);
    fin.getline(B, MAX);    NB=strlen(B);

    int hash1=0, hash2=0;
    if(NA>NB) { fout<<"0\n"; return 0;}
    for(int i=0; i<NA; i++){
        hashA1=(hashA1*base1 + A[i])%MOD1;
        hashA2=(hashA2*base1 + A[i])%MOD2;
        hash1=(hash1*base1 + B[i])%MOD1;
        hash2=(hash2*base1 + B[i])%MOD2;
        if(i!=0) P1*=base1,
                 P2*=base1;
    }
    if(hashA1==hash1 && hashA2==hash2)
        sol[++sol[0]]=1;

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

        if(hash1==hashA1 && hash2==hashA2){
            sol[0]++;
            if(sol[0]<=1000) sol[sol[0]]=i+1;
        }
    }
    fout<<sol[0]<<"\n";
    for(int i=1; i<=min(1000, sol[0]); i++)
        fout<<sol[i]<<" ";

    fin.close();
    fout.close();
    return 0;
}