Cod sursa(job #1543103)

Utilizator Nevermore10Macovei Cosmin Nevermore10 Data 5 decembrie 2015 22:30:02
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <iostream>
#include <cstring>
#define M1 100129
#define M2 99923
// pt hashuri - 100129 , 99923
// 257 - ca baza || sau 257
// LC
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001], b[2000001];
int hashA,hashB,hashA2,hashB2,nr = 0;
int pozitii[2000000];
int pwr(int baza, int exp, int M) {
    int rez = 1, power = baza;
    while(exp) {
        if(exp & 1) {
            rez = (rez*power) % M;

        }
        power = (power*power)%M;
        exp >>=1;
    }
    return rez;
}
int contor = 0;
int main() {
    f.getline(a,2000000,'\n');
    f.getline(b,2000000, '\n');
    int length_a = strlen(a);
    int length_b = strlen(b);
    for(int i = 0; i < length_a; i++) {
        hashA = (hashA + (int)a[i] * pwr(257,length_a - i - 1,M1));
        hashA2 = (hashA2 + (int)a[i] * pwr(257,length_a - i - 1,M2));
    }
    hashA %= M1;
    hashA2 %= M2;
    for(int i = 0; i < length_a; i++) {
        hashB = (hashB + (int)b[i] * pwr(257,length_a - i - 1,M1));
        hashB2 = (hashB2 + (int)b[i] * pwr(257,length_a - i - 1,M2));
    }
    hashB = hashB % M1;
    hashB2 %= M2;
    if(hashA == hashB && hashA2 == hashB2) {
        pozitii[contor] = 0;
        contor++;
        nr++;
    }
    for(int i = length_a; i < length_b; i++) {
        hashB = ((hashB*257 + (int)b[i])  - (b[i-length_a] * pwr(257,length_a,M1) ) %M1 + M1) % M1;
        hashB2 = ((hashB2*257 + (int)b[i]) - (b[i-length_a] * pwr(257,length_a,M2)) % M2 + M2) % M2;
        hashB %= M1;
        hashB2 %= M2;
        if(hashA == hashB && hashA2 == hashB2) {
          nr++;
          pozitii[contor++] = i-length_a + 1;
          if(nr == 1000) {
            break;
          }
        }
    }
    g << nr << "\n";
    for(int j = 0; j < nr; j++) {
        g << pozitii[j] << " ";
    }
}