Cod sursa(job #2427988)

Utilizator NineshadowCarapcea Antonio Nineshadow Data 3 iunie 2019 11:17:19
Problema Potrivirea sirurilor Scor 14
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 2000005
#define MOD 666013



long hash(char *str, int len) {
    long hash = 0;
    for(int i = 0; i < len; ++i) {
        hash = (hash * 32 + str[i]) % MOD;
        
    }
    return hash;
}
int main() {
    char text[MAXN], sablon[MAXN];
    int sol[10000], k = 0;
    FILE *in = fopen("strmatch.in", "r");
    fgets(sablon, MAXN, in);
    fgets(text, MAXN, in);
    fclose(in);
    int n = strlen(text) - 1, m = strlen(sablon) - 1;
    sablon[m] = 0;
    text[n] = 0;
    long hash_sablon = 0, rolling_hash = 0;
    for(int i = 0; i < m; ++i) {
        hash_sablon = (hash_sablon * 32 + sablon[i]) % MOD;
        rolling_hash = (rolling_hash * 32 + text[i]) % MOD;
    }
    long pow = 1;
    for(int i = 1; i <= m - 1; ++i) {
        pow *= 32;
        
    }
    if(hash_sablon == rolling_hash) {
        printf("%d ", 0);
        return 0;
    }
    
    for(int i = 1; i < n - m + 1; ++i) {
        
        rolling_hash = (((rolling_hash + 32 * MOD - pow * text[i - 1]) * 32) % MOD + text[i + m - 1]) % MOD;
        
        if(rolling_hash == hash_sablon) {
            int ok = 1;
            for(int j = 0; j < m; ++j) {
                if(sablon[j] != text[i + j]) {
                    ok = 0;
                    break;
                }
            }

            if(ok) {
                sol[k++] = i;
                //printf("Am gasit la %d\n", i);
            }
        }
    }
    FILE *out = fopen("strmatch.out", "w");
    fprintf(out, "%d\n", k);
    for(int i = 0; i < k; ++i) {
        fprintf(out, "%d ", sol[i]);
    }
    fprintf(out, "\n");
    fclose(out);
    

    
}