Cod sursa(job #2344142)

Utilizator RK_05Ivancu Andreea Raluca RK_05 Data 14 februarie 2019 20:00:09
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 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 << '\n';

    for(i = 0; i < da; i++)

        fout << v[i] << " ";

    fin.close();

    fout.close();

    return 0;

}