Cod sursa(job #2169110)

Utilizator RK_05Ivancu Andreea Raluca RK_05 Data 14 martie 2018 13:29:33
Problema Potrivirea sirurilor Scor 6
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <cstring>
#include <cmath>

using namespace std;

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

int h1, h2, v[2000000];

int create_hash1(char pat[], int &j){
    int i, n = strlen(pat);
    for(i = 0; i < n; i++){
        j = j + (pat[i] - 'a' + 1) * powl(3, i);
    }
    return j;
}
int create_hash2(char pat[], int &j){
    int i, n = strlen(pat);
    for(i = 0; i < n; i++){
        j = j + (pat[i] - 'a' + 1) * powl(5, i);
    }
    return j;
}
int rabin_karp(char text[], char pat[], int h1, int h2, int v[]){
    int i, j, k = 0, c = 1, m = strlen(text), n = strlen(pat), g1, g2;
    char p[n];
    for(i = 0; i < m; i++){
        g1 = 0; g2 = 0;
        for(j = 0; j < n; j++)
            p[j] = text[i + j];
        create_hash1(p, g1);
        create_hash2(p, g2);
        if(h1 == g1 && h2 == g2){
                v[k] = i;
                k++;
            }
        }
    return k;
}

int main()
{
    char text[1000000], pat[1000000];
    fin >> pat >> text;
    int da, i;
    h1 = create_hash1(pat, h1);
    h2 = create_hash2(pat, h2);
    da = rabin_karp(text, pat, h1, h2, v);
    fout << da << endl;
    for(i = 0; i < da; i++)
        fout << v[i] << " ";
    fin.close();
    fout.close();
    return 0;
}