Cod sursa(job #2792329)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 1 noiembrie 2021 14:37:14
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.6 kb
#include <stdio.h>
#include <vector>
#include <string>
#include <string.h>

FILE *fin, *fout;

const int DIM = 2e6;
const int P1 = 67;
const int P2 = 61;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;

int N, M, cnt;
std :: string a, b;
std :: vector<int>ans;
int hash_a1, hash_a2, hash_b1, hash_b2;

inline int value(char a) {
    if(isupper(a)) {
        return a - 'A';
    }
    if(islower(a)) {
        return a - 'a' + 26;
    }
    if(isdigit(a)) {
        return a - '0' + 26 + 26;
    }
    return 0;
}

void read_string(std :: string &buffer, int DIM, FILE *fin) {
    for(int i = 0, ch; i < DIM && (ch = fgetc(fin)) != EOF && ch != '\n'; i++) {
        buffer.push_back((char)ch);
    }
    buffer.push_back('\0');
}

void write_string(const std :: string &buffer, FILE *fout) {
    for(int i = 0; buffer[i] != '\0'; i++) {
        fputc(buffer[i], fout);
    }
}

int main() {
    fin = fopen("strmatch.in", "r");
    fout = fopen("strmatch.out", "w");

    read_string(a, DIM + 1, fin);
    read_string(b, DIM + 1, fin);

    N = a.size();
    M = b.size();

    if(N > M) {
        fprintf(fout, "0\n");
        return 0;
    }

    int p1 = 1, p2 = 1;
    for(int i = 0; i < N; i++) {
        hash_a1 = ((long long)P1 * hash_a1 % MOD1 + value(a[i])) % MOD1;
        hash_a2 = ((long long)P2 * hash_a2 % MOD2 + value(a[i])) % MOD2;

        if(i != N - 1) {
            p1 = (long long)p1 * P1 % MOD1;
            p2 = (long long)p2 * P2 % MOD2;
        }
    }

    for(int i = 0; i < N; i++) {
        hash_b1 = ((long long)P1 * hash_b1 % MOD1 + value(b[i])) % MOD1;
        hash_b2 = ((long long)P2 * hash_b2 % MOD2 + value(b[i])) % MOD2;
    }

    if(hash_a1 == hash_b1 && hash_a2 == hash_b2) {
        cnt = 1;
        ans.push_back(0);
    }

//    printf("%d %d\n", p1, p2);

    for(int i = N; i < M; i++) {
//        printf("%d %d\n", hash_b1, hash_b2);
        hash_b1 = ((long long)hash_b1 - (long long)value(b[i - N]) * p1 % MOD1 + MOD1) % MOD1;
        hash_b2 = ((long long)hash_b2 - (long long)value(b[i - N]) * p2 % MOD2 + MOD2) % MOD2;

        hash_b1 = ((long long)hash_b1 * P1 % MOD1 + value(b[i])) % MOD1;
        hash_b2 = ((long long)hash_b2 * P2 % MOD2 + value(b[i])) % MOD2;

        if(hash_a1 == hash_b1 && hash_a2 == hash_b2) {
            if(++cnt <= 1000) {
                ans.push_back(i - N + 1);
            }
        }

    }

    fprintf(fout, "%d\n", cnt);
    for(int i = 0; i < ans.size(); i++) {
        fprintf(fout, "%d ", ans[i]);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}