TriMill's stats

#[derive(Clone)]
struct Substring {
  idx: usize,
  s: Vec<u8>
}

pub fn entry(needle: &str, haystack: &str) -> Option<usize> {
  let bytes = needle.bytes().collect::<Vec<u8>>();
  let substrs = substrings(haystack.bytes().collect(), 0);
  substrs.iter().filter(|x| x.s == bytes).next().map(|x| x.idx)
}

fn substrings(mut s: Vec<u8>, idx: usize) -> Vec<Substring> {
  if s.len() == 0 {
    return vec![Substring { idx, s: vec![] }]
  }
  let first = s.remove(0);
  let substrs = substrings(s, idx+1);
  let mut result = vec![Substring { idx, s: vec![] }];
  for substr in substrs {
    result.push(substr.clone());
    if substr.idx == idx + 1 {
      let mut bytes = substr.s.clone();
      bytes.insert(0, first);
      result.push(Substring { idx, s: bytes  });
    }
  }
  result
}

#include <stdio.h>
#include <stdlib.h>

int fib(int n, int** a, size_t* u, size_t* s) {
    if(n < 0) {
        size_t u = 2;
        size_t s = 10;
        int* a = malloc(s * sizeof(int));
        int t = 0;
        while(n + t != -1) {
            int q = 0;
            int r;
            while(1) {
                r = fib(q, &a, &u, &s);
                if(-r - 1 < n + t) {
                    break;
                }
                q += 1;
            }
            int f = fib(q-1, &a, &u, &s);
            t += f;
            printf("%d ", q-1);
        }
        printf("\n");
    } else if(n < 2) {
        return n;
    } else if(n < *u) {
        return (*a)[n];
    } else {
        int next = fib(n-1, a, u, s) + fib(n-2, a, u, s);
        if (*u == *s) {
            *s *= 2;
            *a = realloc(*a, *s * sizeof(int));
        }
        (*a)[(*u)++] = next;
        return next;
    }
}

void fib2() {
    int goal;
    scanf("%d", &goal);
    fib(-goal-1, NULL, NULL, NULL);
}

int main() {
    fib2();
    return 0;
}