#ifndef prototype1_src_l1_5_core_stringsearch_h
#define prototype1_src_l1_5_core_stringsearch_h

#include "../../l1/core/VecU8_as_str.h"
#include "../../../gen/l1/VecAndSpan_U64.h"

NODISCARD VecU64 prefix_function(SpanU8 s){
    VecU64 prefix = VecU64_new_zeroinit(s.len + 1);
    for (size_t i = 1; i < s.len; i++) {
        size_t k = prefix.buf[i];
        while (k > 0 && s.data[k] != s.data[i])
            k = prefix.buf[k];
        if (s.data[k] == s.data[i])
            k++;
        prefix.buf[i + 1] = k;
    }
    return prefix;
}


NODISCARD VecU64 z_function(SpanU8 s){
    VecU64 Z = VecU64_new_zeroinit(s.len + 1);
    Z.buf[0] = s.len;
    size_t l = 0, r = 0;
    for (size_t i = 1; i <= s.len; i++) {
        if (i + 1 < r) {
            Z.buf[i] = MIN_U64(r - i, Z.buf[i - l]);
        }
        while (i + Z.buf[i] < s.len && s.data[Z.buf[i]] == s.data[i + Z.buf[i]]) {
            Z.buf[i]++;
        }
        if (i + Z.buf[i] >= r) {
            l = i;
            r = i + Z.buf[i];
        }
    }
    return Z;
}


#endif

