Cod sursa(job #1727025)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 9 iulie 2016 18:33:36
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.65 kb


#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <math.h>

#define NMAX 2000005

char str_a[NMAX], str_b[NMAX];
int ans[NMAX];

const int M = 3666013;

int k_to_the_n;

int _min (int a, int b) {
    return a < b ? a : b;
}

long long compute_hash (char pattern[], int length) {

    int i;
    int q = 0x100;
    long long k = 1;
    long long hash = 0;
    for (i = 0; i < length; ++i) {
        hash = (hash + pattern[length - i - 1] * k) % M;
        k_to_the_n = k;
        k = k * q % M;
    }

    return hash;

}

int _str_cmp (char str1[], char str2[], int length) {
    int i;
    for (i = 0; i < length; ++i) {
        if (str1[i] != str2[i])
            return 0;
    }
    return 1;
}

int main () {

    int i, ans_ind = 0;

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf ("%s", str_a);
    scanf ("%s", str_b);

    int len_a = strlen(str_a),
        len_b = strlen(str_b);

    long long hash_for_a = compute_hash(str_a, len_a);
    long long init_hash = compute_hash(str_b, len_a);

    if (init_hash == hash_for_a && _str_cmp(str_a, str_b, len_a)) {
        ans[ans_ind++] = 0;
    }

    for (i = len_a; i < len_b; ++i) {
       
       init_hash -= str_b[i - len_a] * k_to_the_n;
       while (init_hash < 0) init_hash += M;

       init_hash = init_hash * 0x100 % M;
       init_hash = (init_hash + str_b[i]) % M;

       if (init_hash == hash_for_a && _str_cmp(str_a, str_b + i - len_a + 1, len_a)) {
            ans[ans_ind++] = i - len_a + 1;
       }

    }

    int k = _min (ans_ind, 1000);
    printf ("%d\n", ans_ind);
    for (i = 0; i < k; ++i) {
        printf ("%d ", ans[i]);
    }

}