Cod sursa(job #2169056)

Utilizator RK_05Ivancu Andreea Raluca RK_05 Data 14 martie 2018 13:18:53
Problema Potrivirea sirurilor Scor 22
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <cstring>
#include <cmath>

using namespace std;

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

int h, v[2000000];

int create_hash(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 rabin_karp(char text[], char pat[], int h, int v[]){
    int i, j, k = 0, c = 1, m = strlen(text), n = strlen(pat), g;
    char p[n];
    for(i = 0; i < m; i++){
        g = 0;
        for(j = 0; j < n; j++)
            p[j] = text[i + j];
        create_hash(p, g);
        if(h == g){
            c = 1;
            for(j = 0; j < n; j++)
                if(pat[j] != p[j]){
                    c = 0;
                    break;
                }
            if(c == 1){
                v[k] = i;
                k++;
            }
        }
    }
    return k;
}

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