Cod sursa(job #1328173)

Utilizator theprdvtheprdv theprdv Data 28 ianuarie 2015 05:29:38
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 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 27
#define base2 29

char N[MAX], M[MAX], sub[MAX];
int n, m;
int p_hash1, p_hash2, s_hash1, s_hash2, sol[MAX];

int main()
{
    int P1=1, P2=1;
    fin.getline(N, MAX);    n=strlen(N);
    fin.getline(M, MAX);    m=strlen(M);

    if(n>m) { fout<<"00\n"; return 0;}
    for(int i=0; i<n; i++){
        p_hash1=(p_hash1*base1 + N[i])%MOD1;
        p_hash2=(p_hash2*base2 + N[i])%MOD2;
        s_hash1=(s_hash1*base1 + M[i])%MOD1;
        s_hash2=(s_hash2*base2 + M[i])%MOD2;
        if(i!=0) P1*=base1,
                 P2*=base2;
    }
    if(p_hash1==s_hash1 && p_hash2==s_hash2)
        sol[++sol[0]]=1;

    for(int i=0; i<m-n; i++){
        s_hash1=((s_hash1-(P1*M[i])%MOD1+MOD1)*base1+M[n+i])%MOD1;
        s_hash2=((s_hash2-(P2*M[i])%MOD2+MOD2)*base2+M[n+i])%MOD2;

        if(s_hash1==p_hash1 && s_hash2==p_hash2){
            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;
}