Algorithms: String Algorithms

function z_array(array $a, array &$output): int {
    alg_require(array_is_list($a));
    alg_require(array_is_list($output));
    $n = count($a);
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((count($a) == $n));
    alg_require((count($output) == $n));
    $left = 0;
    $right = 0;
    $i = 0;
    while (($i < $n)) {
        $output[$i] = 0;

def kmp_match(text: list[int], pattern: list[int]) -> int:
    alg_require(isinstance(text, (list, tuple)) and len(text) <= 1000000)
    alg_require(isinstance(pattern, (list, tuple)) and len(pattern) <= 1000000)
    n: int = len(text)
    m: int = len(pattern)
    alg_require(n >= 0 and n <= 1000000)
    alg_require(m >= 0 and m <= 1000000)
    alg_require(len(pattern) == m)
    alg_require(len(text) == n)
    if m == 0:
        return 0
    prefix: list[int] = [0] * alg_size(m + 1)

int kmp_match(const int *text, size_t text_length, const int *pattern, size_t pattern_length) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    int *prefix = NULL;
    if (text_length > 1000000 || (text_length && !text)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (pattern_length > 1000000 || (pattern_length && !pattern)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    int n = (int)text_length;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int m = (int)pattern_length;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((n >= 0) && (n <= 1000000)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }

int kmp_match(const std::vector<int>& text, const std::vector<int>& pattern) {
    alg_require(text.size() <= 1000000);
    alg_require(pattern.size() <= 1000000);
    int n = (int)text.size();
    int m = (int)pattern.size();
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require(((m >= 0) && (m <= 1000000)));
    alg_require(((int)pattern.size() == m));
    alg_require(((int)text.size() == n));
    if ((m == 0)) {
        return 0;
    }

    static int kmp_match(ReadOnlySpan<int> text, ReadOnlySpan<int> pattern) {
        checked {
            int n = text.Length;
            int m = pattern.Length;
            alg_require(((n >= 0) && (n <= 1000000)));
            alg_require(((m >= 0) && (m <= 1000000)));
            alg_require((pattern.Length == m));
            alg_require((text.Length == n));
            if ((m == 0)) {
                return 0;
            }
            int[] prefix = new int[alg_size((m + 1))];