Cod sursa(job #2045007)

Utilizator ciocirlanrCiocirlan Robert ciocirlanr Data 21 octombrie 2017 17:57:29
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

#define d 256

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


vector <int> rez;
char subsir[2000002],sir[2000002];
int q = 101; /// Numar Prim
int sol;

void rk(char subsir[], char sir[], int q) {

    int M = strlen(subsir);
    int N = strlen(sir);
    int i,j;
    int p = 0; // valoare hash pentru subsir
    int t = 0; // valoare hash pentru sir
    int h = 1;

    // valoarea lui h este  "pow(d, M-1)%q"
    for (i = 0; i < M-1; i++)
        h = (h*d)%q;

    //Calculam valoarea hash pentru subsir si prima portiune de text
    for (i = 0; i < M; i++) {
        p = (d*p + subsir[i])%q;
        t = (d*t + sir[i])%q;
    }

    //Punem subsirul peste sir unul cate unul
    for (i = 0; i <= N - M; i++) {

        //Daca hashurile sunt egale cautam caracter cu caracter
        if ( p == t ) {

            for (j = 0; j < M; j++) {
                if (sir[i+j] != subsir[j])
                    break;
            }

            // daca p == t si subsir[0...M-1] = sir[i, i+1, ...i+M-1]
            if (j == M) {
                sol++;
                if(sol <= 1000)
                    rez.push_back(i);
            }
        }

        // Calculam valoarea hash pentru urmatoarea portiune de text
        if ( i < N-M ) {
            t = (d*(t - sir[i]*h) + sir[i+M])%q;

            //Valoarea lui t poate sa fie < 0 => o facem > 0
            if (t < 0)
            t = (t + q);
        }
    }
}

int main(){

    in >> subsir >> sir;

    rk(subsir, sir, q);

    out << sol << '\n';

    for(int i=0; i < rez.size(); ++i) out << rez[i] << ' ';

    return 0;
}