Cod sursa(job #2794699)

Utilizator DajaMihaiDaja Mihai DajaMihai Data 5 noiembrie 2021 12:10:56
Problema Potrivirea sirurilor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <cstdio>
#include <cstring>
#define MAX 2000000

using namespace std;

char strA [MAX], strB[MAX];
int i, Hash, fHash, j, cntPoz, check;
int Poz [1000];

int compute (char v[], int length){
    int y, hash;
    y = hash = 0;
    while (y < length){
        hash += v[y];
        y ++;
    }
    return hash;
}

int addHash (char c, int var){
    return var + (int) c;
}

int removeHash (char c, int var){
    return var - (int) c;
}

int checkString (int a, int h){
    int l;
    l = 0;
    while (l <= h){
        if (strB[a + l - 1] != strA [l])
            return 1;
        l ++;
    }
    return 0;
}


int main() {

    FILE *in, *out;
    in = fopen("strmatch.in", "r");
    out = fopen("strmatch.out", "w");

    i --; // calc valoarea hash-ului stringului A
    while (strA[i] != '\n'){
        check = fgetc(in);
        strA [++i] = check;
        Hash = addHash (strA[i], Hash);
    }
    Hash -= 10;
    i --;

    //calc valoarea hash-ului primelor i charactere unde i este lungimea primului Hash
    for (j = 0; j <= i; j ++)
        strB [j] = fgetc (in);
    fHash = compute (strB, j);

    //LastPos indica unde se afla in StrB ultimul character al hash-ului
    int LastPos = 0;

    while (((strB[j - 1] >= 'A' && strB[j - 1] <= 'Z')||(strB[j - 1] >= 'a' && strB[j - 1] <= 'z'))&&cntPoz < 1000){

        //verific egalitatea hash-urilor
        if (fHash == Hash ){
            //numai dupa acea verific egalitatea stringurilor
            if (!checkString(j - i, i)) {
                Poz[cntPoz] = LastPos;
                cntPoz ++;
            }
        }

        //scot ultimul numar din hash si adaug primul element din strB
        fHash = removeHash (strB[LastPos], fHash);
        strB [j] = fgetc (in);
        j ++;
        fHash = addHash (strB[j - 1], fHash);
        LastPos ++;
    }

    //afisez rezultatele
    fprintf (out, "%d\n", cntPoz);
    for (int k = 0; k < cntPoz; k ++)
        fprintf (out, "%d ", Poz[k]);
    return 0;
}