A tarefa é contar o número de substrings distintos de comprimento k, para k = 1,2,3,4, .....

Resultado

Você deve imprimir uma linha por kque consiga concluir com um número por linha de saída. Sua saída deve estar em ordem de aumento katé você ficar sem tempo.

Ponto

Sua pontuação é a maior nota que você pode obter no meu computador em menos de 1 minuto.

Você deve usar http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/chr2.fa.gz como sua entrada e ignorar as novas linhas. Seu código, no entanto, diferencia maiúsculas de minúsculas.

Você pode descomprimir a entrada antes de iniciar o tempo.

O código (ineficiente) a seguir conta o número de 4 metros distintos.

awk -v substr_length=4 '(len=length($0))>=substr_length{for (i=1; (i-substr_length)<len; i++) substrs[substr($0,i,substr_length)]++}; END{for (i in substrs) print substrs[i], i}' file.txt|wc

Limites de memória

Para fazer com que seu código se comporte bem no meu computador e para tornar a tarefa mais desafiadora, limitarei a RAM que você pode usar para 2 GB usando

ulimit -v 2000000

antes de executar seu código. Estou ciente de que essa não é uma maneira sólida de limitar o uso de RAM; portanto, não use maneiras imaginativas para contornar esse limite, por exemplo, gerando novos processos. Claro que você pode escrever código multiencadeado, mas se alguém o fizer, terei que aprender a limitar o total de RAM usada para isso.

Desempate

No caso de um empate por um tempo máximo k, cronometrarei quanto tempo leva para produzir os resultados k+1e o mais rápido ganha. No caso em que eles correm ao mesmo tempo em até um segundo k+1, a primeira submissão vence.

Línguas e bibliotecas

Você pode usar qualquer idioma que tenha um compilador / intérprete disponível gratuitamente / etc. para Linux e quaisquer bibliotecas que também estão disponíveis gratuitamente para Linux.

Minha máquina Os horários serão executados na minha máquina. Esta é uma instalação padrão do ubuntu em um processador AMD FX-8350 de oito núcleos em uma placa-mãe Asus M5A78L-M / USB3 (soquete AM3 +, 8GB DDR3). Isso também significa que eu preciso poder executar seu código. Como conseqüência, use apenas software livre facilmente disponível e inclua instruções completas sobre como compilar e executar seu código.

Saída de teste

O código do FUZxxl gera o seguinte (mas não todos em 1 minuto), que acredito estar correto.

14
92
520
2923
15714
71330
265861
890895
2482912
5509765
12324706
29759234

tabela do Campeonato

• k> = 4000 FUZxxl (C)
• k = 16 por Keith Randall (C ++)
• k = 10 por FUZxxl (C)

Quanto você pode especializar seu código na entrada?

• Claramente, isso arruinaria a concorrência se você precomputasse as respostas e o seu código as produzisse. Não faça isso.
• Idealmente, qualquer coisa que seu código precise aprender sobre os dados que ele usará para executar mais rapidamente, em tempo de execução.
• No entanto, você pode assumir que a entrada será semelhante aos dados nos arquivos * .fa em http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .

C (≥ 4000)

Esse código não usa menos de 2 GB de RAM (usa um pouco mais) nem produz qualquer saída no primeiro minuto. Mas se você esperar cerca de seis minutos, ela imprimirá todas as contagens de k- mer de uma só vez.

Uma opção está incluída para limitar o k mais alto pelo qual contamos os k- meros. Quando k é limitado a um intervalo razoável, o código termina em menos de um minuto e usa menos de 2 GiB de RAM. A OP classificou esta solução e termina em menos de um minuto para um limite não superior a 4000.

Como funciona?

O algoritmo possui quatro etapas.

1. Leia o arquivo de entrada em um buffer e retire novas linhas.

2. Classifique com sufixo uma matriz de índices no buffer de entrada. Por exemplo, os sufixos da string mississippisão:

   mississippi
   ississippi
   ssissippi
   sissippi
   issippi
   ssippi
   sippi
   ippi
   ppi
   pi
   i
   

   Essas seqüências classificadas em ordem lexicográfica são:

   i
   ippi
   issippi
   ississippi
   mississippi
   pi
   ppi
   sippi
   sissippi
   ssippi
   ssissippi
   

   É fácil ver que todas as substrings iguais de comprimento k para todos os k são encontradas nas entradas adjacentes da matriz classificada por sufixo.

3. É preenchido um array inteiro no qual armazenamos em cada índice k o número de k- meros distintos . Isso é feito de maneira um pouco complicada para acelerar o processo. Considere duas entradas adjacentes a matriz classificada com sufixo.

      p     l
      v     v
   issippi
   ississippi
   

   p denota o comprimento do prefixo comum mais longo das duas entradas, l denota o comprimento da segunda entrada. Para esse par, encontramos uma nova substring distinta de comprimento k para p < k ≤ l . Como p ≪ l geralmente é válido, não é prático incrementar um grande número de entradas de matriz para cada par. Em vez disso, armazenamos a matriz como uma matriz de diferenças, em que cada entrada k indica a diferença entre o número de k -mers e o número de ( k  - 1) -mers. Isso ativa uma atualização do formulário

   0  0  0  0 +1 +1 +1 +1 +1 +1  0  0  0
   

   em uma atualização muito mais rápida do formulário

   0  0  0  0 +1  0  0  0  0  0 -1  0  0
   

   Observando cuidadosamente que l é sempre diferente e, de fato, cada 0 < l < n aparecerá exatamente uma vez, podemos omitir as subtrações e, em vez disso, subtrair 1 de cada diferença ao converter as diferenças em quantidades.

4. As diferenças são convertidas em quantidades e impressas.

O código fonte

Essa fonte usa o libdivsufsort para classificar matrizes de sufixos. O código gera saída de acordo com a especificação quando compilado com esta chamada.

cc -O -o dsskmer dsskmer.c -ldivsufsort

alternativamente, o código pode gerar saída binária quando compilado com a seguinte chamada.

cc -O -o dsskmer -DBINOUTPUT dsskmer.c -ldivsufsort

Para limitar o k mais alto para o qual k- meros devem ser contados, forneça -DICAP = k onde k é o limite:

cc -O -o dsskmer -DICAP=64 dsskmer.c -ldivsufsort

Compile com -O3se o seu compilador fornecer essa opção.

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

#include <divsufsort.h>

#ifndef BINOUTPUT
static char stdoutbuf[1024*1024];
#endif

/*
 * load input from stdin and remove newlines. Save length in flen.
 */
static unsigned char*
input(flen)
    int *flen;
{
    size_t n, len, pos, i, j;
    off_t slen;
    unsigned char *buf, *sbuf;

    if (fseek(stdin, 0L, SEEK_END) != 0) {
        perror("Cannot seek stdin");
        abort();
    }

    slen = ftello(stdin);
    if (slen == -1) {
        perror("Cannot tell stdin");
        abort();
    }

    len = (size_t)slen;

    rewind(stdin);

    /* Prepare for one extra trailing \0 byte */
    buf = malloc(len + 1);
    if (buf == NULL) {
        perror("Cannot malloc");
        abort();
    }

    pos = 0;

    while ((n = fread(buf + pos, 1, len - pos, stdin)) != 0)
        pos += n;

    if (ferror(stdin)) {
        perror("Cannot read from stdin");
        abort();
    }

    /* remove newlines */
    for (i = j = 0; i < len; i++)
        if (buf[i] != '\n')
            buf[j++] = buf[i];

    /* try to reclaim some memory */
    sbuf = realloc(buf, j);
    if (sbuf == NULL)
        sbuf = buf;

    *flen = (int)j;
    return sbuf;
}

/*
 * Compute for all k the number of k-mers. kmers will contain at index i the
 * number of (i + 1) mers. The count is computed as an array of differences,
 * where kmers[i] == kmersum[i] - kmersum[i-1] + 1 and then summed up by the
 * caller. This algorithm is a little bit unclear, but when you write subsequent
 * suffixes of an array on a piece of paper, it's easy to see how and why it
 * works.
 */
static void
count(buf, sa, kmers, n)
    const unsigned char *buf;
    const int *sa;
    int *kmers;
{
    int i, cl, cp;

    /* the first item needs special treatment */
    kmers[0]++;

    for (i = 1; i < n; i++) {
        /* The longest common prefix of the two suffixes */
        cl = n - (sa[i-1] > sa[i] ? sa[i-1] : sa[i]);
#ifdef ICAP
        cl = (cl > ICAP ? ICAP : cl);
#endif
        for (cp = 0; cp < cl; cp++)
            if (buf[sa[i-1] + cp] != buf[sa[i] + cp])
                break;

        /* add new prefixes to the table */
        kmers[cp]++;
    }
}

extern int
main()
{
    unsigned char *buf;
    int blen, ilen, *sa, *kmers, i;

    buf = input(&blen);

    sa = malloc(blen * sizeof *sa);

    if (divsufsort(buf, sa, blen) != 0) {
        puts("Cannot divsufsort");
        abort();
    }

#ifdef ICAP
    ilen = ICAP;
    kmers = calloc(ilen + 1, sizeof *kmers);
#else
    ilen = blen;
    kmers = calloc(ilen, sizeof *kmers);
#endif

    if (kmers == NULL) {
        perror("Cannot malloc");
        abort();
    }

    count(buf, sa, kmers, blen);

#ifndef BINOUTPUT
    /* sum up kmers differences */
    for (i = 1; i < ilen; i++)
        kmers[i] += kmers[i-1] - 1;


    /* enlarge buffer of stdout for better IO performance */
    setvbuf(stdout, stdoutbuf, _IOFBF, sizeof stdoutbuf);

    /* human output */
    for (i = 0; i < ilen; i++)
        printf("%d\n", kmers[i]);
#else
    /* binary output in host endianess */
    fprintf(stderr, "writing out result...\n");
    fwrite(kmers, sizeof *kmers, ilen, stdout);
#endif

    return 0;
}

O formato do arquivo binário pode ser convertido no formato de saída legível por humanos com o seguinte programa:

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

static int inbuf[BUFSIZ];
static char outbuf[BUFSIZ];

extern int main()
{
    int i, n, sum = 1;

    setbuf(stdout, outbuf);

    while ((n = fread(inbuf, sizeof *inbuf, BUFSIZ, stdin)) > 0)
        for (i = 0; i < n; i++)
            printf("%d\n", sum += inbuf[i] - 1);

    if (ferror(stdin)) {
        perror("Error reading input");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

saída de amostra

Exemplo de saída no formato binário para o arquivo chr22.fapode ser encontrado aqui . Descompacte bzip2 -dprimeiro. A saída é fornecida no formato binário apenas porque compacta muito melhor (3,5 kB x 260 MB) do que a saída no formato legível por humanos. Cuidado, porém, que a saída de referência tem um tamanho de 924 MB quando descompactada. Você pode querer usar um pipe como este:

bzip2 -dc chr2.kmerdiffdat.bz2 | ./unbin | less

C ++, k = 16, 37 segundos

Calcula todos os 16 mers na entrada. Cada 16-mer é compactado em 4 bits em um símbolo em uma palavra de 64 bits (com um padrão de bit reservado para EOF). As palavras de 64 bits são classificadas. A resposta para cada k pode ser lida observando-se com que frequência os 4 * k bits superiores das palavras classificadas são alterados.

Para a entrada de teste, uso cerca de 1,8 GB, logo abaixo do fio.

Tenho certeza que a velocidade de leitura pode ser melhorada.

Resultado:

14
92
520
2923
15714
71330
265861
890895
2482912
5509765
12324706
29759234
69001539
123930801
166196504
188354964

Programa:

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

int main(int argc, char *argv[]) {
    // read file
    printf("reading\n");
    FILE *f = fopen(argv[1], "rb");
    fseek(f, 0, SEEK_END);
    int32_t size = ftell(f);
    printf("size: %d\n", size);
    fseek(f, 0, SEEK_SET);

    // table to convert 8-bit input into 4-bit tokens.  Reserve 15 for EOF.
    int ntokens = 0;
    int8_t squash[256];
    for(int i = 0; i < 256; i++) squash[i] = -1;

    uint64_t *buf = (uint64_t*)malloc(8*size);

    int32_t n = 0;
    uint64_t z = 0;
    for(int32_t i = 0; i < size; i++) {
        char c = fgetc(f);
        if(c == '\n') continue;
        int8_t s = squash[c];
        if(s == -1) {
            if(ntokens == 15) {
                printf("too many tokens\n");
                exit(1);
            }
            squash[c] = s = ntokens++;
        }
        z <<= 4;
        z += s;
        n++;

        if(n >= 16) buf[n-16] = z;
    }
    for(int32_t i = 1; i < 16; i++) {
        z <<= 4;
        z += 15;
        buf[n-16+i] = z;
    }
    printf("   n: %d\n", n);

    // sort these uint64_t's
    printf("sorting\n");
    std::sort(buf, buf+n);

    for(int32_t k = 1; k <= 16; k++) {
        // count unique entries
        int32_t shift = 64-4*k;
        int32_t cnt = 1;
        int64_t e = buf[0] >> shift;
        for(int32_t i = 1; i < n; i++) {
            int64_t v = buf[i] >> shift;
            if((v & 15) == 15) continue; // ignore EOF entries
            if(v != e) {
                cnt++;
                e = v;
            }
        }

        printf("%d\n", cnt);
    }
}

Compilar g++ -O3 kmer.cc -o kmere executar com ./kmer chr2.fa.

C ++ - uma melhoria em relação à solução FUZxxl

Eu não mereço absolutamente nenhum crédito pelo próprio método de computação e, se nenhuma abordagem melhor aparecer nesse meio tempo, a recompensa deve ir para a FUZxxl à direita.

#define _CRT_SECURE_NO_WARNINGS // a Microsoft thing about strcpy security issues
#include <vector>

#include <string>
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;

#include "divsufsort.h"

// graceful exit of sorts
void panic(const char * msg)
{
    cerr << msg;
    exit(0);
}

// approximative timing of various steps
struct tTimer {
    time_t begin;
    tTimer() { begin = time(NULL); }
    void print(const char * msg)
    {
        time_t now = time(NULL);
        cerr << msg << " in " << now - begin << "s\n";
        begin = now;
    }
};

// load input pattern
unsigned char * read_sequence (const char * filename, int& len)
{
    ifstream file(filename);
    if (!file) panic("could not open file");

    string str;
    std::string line;
    while (getline(file, line)) str += line;
    unsigned char * res = new unsigned char[str.length() + 1];
    len = str.length()+1;
    strcpy((char *)res, str.c_str());
    return res;
}

#ifdef FUZXXL_METHOD
/*
* Compute for all k the number of k-mers. kmers will contain at index i the
* number of (i + 1) mers. The count is computed as an array of differences,
* where kmers[i] == kmersum[i] - kmersum[i-1] + 1 and then summed up by the
* caller. This algorithm is a little bit unclear, but when you write subsequent
* suffixes of an array on a piece of paper, it's easy to see how and why it
* works.
*/
static void count(const unsigned char *buf, const int *sa, int *kmers, int n)
{
    int i, cl, cp;

    /* the first item needs special treatment */
    /*
        kuroi neko: since SA now includes the null string, kmers[0] is indeed 0 instead of 1
    */
//  kmers[0]++;

    for (i = 1; i < n; i++) {
        /* The longest common prefix of the two suffixes */
        cl = n - (sa[i - 1] > sa[i] ? sa[i - 1] : sa[i]);
#ifdef ICAP
        cl = (cl > ICAP ? ICAP : cl);
#endif
        for (cp = 0; cp < cl; cp++)
        if (buf[sa[i - 1] + cp] != buf[sa[i] + cp])
            break;

        /* add new prefixes to the table */
        kmers[cp]++;
    }
}

#else // Kasai et al. method

// compute kmer cumulative count using Kasai et al. LCP construction algorithm
void compute_kmer_cumulative_sums(const unsigned char * t, const int * sa, int * kmer, int len)
{
    // build inverse suffix array
    int * isa = new int[len];
    for (int i = 0; i != len; i++) isa[sa[i]] = i;

    // enumerate common prefix lengths
    memset(kmer, 0, len*sizeof(*kmer));
    int lcp = 0;
    int limit = len - 1;
    for (int i = 0; i != limit; i++)
    {
        int k = isa[i];
        int j = sa[k - 1];
        while (t[i + lcp] == t[j + lcp]) lcp++;

        // lcp now holds the kth longest commpn prefix length, which is just what we need to compute our kmer counts
        kmer[lcp]++;
        if (lcp > 0) lcp--;
    }
    delete[] isa;
}

#endif // FUZXXL_METHOD

int main (int argc, char * argv[])
{
    if (argc != 2) panic ("missing data file name");

    tTimer timer;
    int blen;
    unsigned char * sequence;
    sequence = read_sequence(argv[1], blen);
    timer.print("input read");

    vector<int>sa;
    sa.assign(blen, 0);
    if (divsufsort(sequence, &sa[0], blen) != 0) panic("divsufsort failed");
    timer.print("suffix table constructed");

    vector<int>kmers;
    kmers.assign(blen,0);

#ifdef FUZXXL_METHOD
    count(sequence, &sa[0], &kmers[0], blen);
    timer.print("FUZxxl count done");
#else
    compute_kmer_cumulative_sums(sequence, &sa[0], &kmers[0], blen);
    timer.print("Kasai  count done");
#endif

    /* sum up kmers differences */
    for (int i = 1; i < blen; i++) kmers[i] += kmers[i - 1] - 1;
    timer.print("sum done");

    /* human output */

    if (blen>10) blen = 10; // output limited to the first few values to avoid cluttering display or saturating disks

    for (int i = 0; i != blen; i++) printf("%d ", kmers[i]);
    return 0;
}

Simplesmente usei Kasai et al. algoritmo para calcular LCPs em O (n).
O resto é uma mera adaptação do código FUZxxl, usando recursos C ++ mais concisos aqui e ali.

Deixei o código de computação original para permitir comparações.

Como os processos mais lentos são a construção de SA e a contagem de LCP, removi a maioria das outras otimizações para evitar sobrecarregar o código para obter ganhos negligenciáveis.

Estendi a tabela SA para incluir o prefixo de comprimento zero. Isso facilita a computação do LCP.

Não forneci uma opção de limitação de comprimento, sendo o processo mais lento agora o cálculo do SA que não pode ser reduzido (ou pelo menos não vejo como poderia ser).

Também removi a opção de saída binária e a exibição limitada aos 10 primeiros valores.
Suponho que esse código seja apenas uma prova de conceito; portanto, não é necessário desorganizar as telas ou saturar os discos.

Construindo o executável

Eu tive que compilar todo o projeto (incluindo a versão litedivsufsort ) do x64 para superar o limite de alocação do Win32 2Gb.

divsufsortO código lança vários avisos devido ao uso intenso de ints em vez de size_ts, mas isso não será um problema para entradas abaixo de 2 GB (que exigiriam 26 GB de RAM de qualquer maneira: D).

Compilação Linux

compile main.cppe divsufsort.cuse os comandos:

g++ -c -O3 -fomit-frame-pointer divsufsort.c 
g++ -O3 main.cpp -o kmers divsufsort.o

Suponho que a divsufsortbiblioteca regular funcione bem no Linux nativo, desde que você possa alocar um pouco mais do que 3Gb.

Performances

O algoritmo Kasai requer a tabela SA inversa, que consome mais 4 bytes por caractere, totalizando 13 (em vez de 9 com o método FUZxxl).

O consumo de memória para entrada de referência é, portanto, acima de 3Gb.

Por outro lado, o tempo de computação é dramaticamente aprimorado e todo o algoritmo agora está em O (n):

input read in 5s
suffix table constructed in 37s
FUZxxl count done in 389s
Kasai  count done in 27s
14 92 520 2923 15714 71330 265861 890895 2482912 5509765 (etc.)

Outras melhorias

A construção da SA é agora o processo mais lento.
Alguns bits do divsufsortalgoritmo devem ser paralelos a qualquer recurso interno de um compilador desconhecido para mim, mas, se necessário, o código deve ser fácil de se adaptar a multithreading mais clássico ( à exemplo do C ++ 11).
A lib também possui uma carga de parâmetros, incluindo vários tamanhos de balde e o número de símbolos distintos na cadeia de entrada. Eu só dei uma olhada superficial neles, mas suspeito que comprimir o alfabeto pode valer a pena tentar se suas cordas forem infinitas permutações de ACTG ( e você estiver desesperado por apresentações).

Também existem alguns métodos paralelizáveis ​​para calcular o LCP a partir do SA, mas como o código deve ser executado em menos de um minuto em um processador um pouco mais poderoso que o meu insignificante [email protected] e todo o algoritmo está em O (n), duvido disso. valeria a pena o esforço.

C (pode resolver até 10 em um minuto na minha máquina)

Esta é uma solução muito simples. Ele constrói uma árvore dos k -mers encontrados e os conta. Para economizar memória, os caracteres são primeiro convertidos em números inteiros de 0 a n - 1, em que n é o número de caracteres diferentes na entrada, portanto, não precisamos fornecer espaço para caracteres que nunca aparecem. Além disso, menos memória é alocada para as folhas do que para outros nós, para economizar mais memória. Esta solução usa cerca de 200 MiB de RAM durante o tempo de execução na minha máquina. Ainda estou melhorando, então talvez na iteração seja ainda mais rápido!

Para compilar, salve o código abaixo em um arquivo nomeado kmers.ce execute em um sistema operacional semelhante ao POSIX:

cc -O -o kmers kmers.c

Você pode querer substituir -O3para -Ose suas sustentações do compilador que. Para executar, primeiro descompactar chr2.fa.gzem chr2.fae execute:

./kmers <chr2.fa

Isso produz a saída passo a passo. Você pode limitar o tempo e o espaço. Use algo como

( ulimit -t 60 -v 2000000 ; ./kmers <chrs.fa )

reduzir os recursos conforme necessário.

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

/*
 * A tree for the k-mers. It contains k layers where each layer is an
 * array of struct tr. The last layer contains a 1 for every kmer found,
 * the others pointers to the next layer or NULL.
 */
struct tr {
    struct tr *n;
};

/* a struct tr to point to */
static struct tr token;

static void     *mem(size_t s);
static int       add(struct tr*, unsigned char*, int, size_t);
static unsigned char    *input(size_t*);
extern int       main(void);

/*
 * Allocate memory, fail if we can't.
 */
static void*
mem(s)
    size_t s;
{
    void *p;

    p = calloc(s, 1);
    if (p != NULL)
        return p;

    perror("Cannot malloc");
    abort();
}

/*
 * add s to b, return 1 if added, 0 if present before. Assume that n - 1 layers
 * of struct tr already exist and only add an n-th layer if needed. In the n-th
 * layer, a NULL pointer denotes non-existance, while a pointer to token denotes
 * existance.
 */
static int
add(b, s, n, is)
    struct tr *b;
    unsigned char *s;
    size_t is;
{
    struct tr **nb;
    int added;
    int i;

    for (i = 0; i < n - 2; i++) {
        b = b[s[i]].n;
    }

    nb = &b[s[n - 2]].n;

    if (*nb == NULL || *nb == &token)
        *nb = mem(is * sizeof *b);

    added = (*nb)[s[n - 1]].n == NULL;
    (*nb)[s[n - 1]].n = &token;

    return (added);
}

/*
 * load input from stdin and remove newlines. Save length in flen.
 */
static unsigned char*
input(flen)
    size_t *flen;
{
    size_t n, len, pos, i, j;
    unsigned char *buf;

    if (fseek(stdin, 0L, SEEK_END) != 0) {
        perror("Cannot seek stdin");
        abort();
    }

    len = ftello(stdin);
    if (len == -1) {
        perror("Cannot tell stdin");
        abort();
    }

    rewind(stdin);

    /* no need to zero out, so no mem() */
    buf = malloc(len);
    if (buf == NULL) {
        perror("Cannot malloc");
        abort();
    }

    pos = 0;

    while ((n = fread(buf + pos, 1, len - pos, stdin)) != 0)
        pos += n;

    if (ferror(stdin)) {
        perror("Cannot read from stdin");
        abort();
    }

    /* remove newlines */
    for (i = j = 0; i < len; i++)
        if (buf[i] != '\n')
            buf[j++] = buf[i];

    *flen = j;
    return buf;
}

extern int
main()
{
    struct tr *b;
    size_t flen, c, i, k, is;
    unsigned char *buf, itab[1 << CHAR_BIT];

    buf = input(&flen);

    memset(itab, 0, sizeof itab);

    /* process 1-mers */
    for (i = 0; i < flen; i++)
        itab[buf[i]] = 1;

    is = 0;
    for (i = 0; i < sizeof itab / sizeof *itab; i++)
        if (itab[i] != 0)
            itab[i] = is++;

    printf("%zd\n", is);

    /* translate characters into indices */
    for (i = 0; i < flen; i++)
        buf[i] = itab[buf[i]];

    b = mem(is * sizeof *b);

    /* process remaining k-mers */
    for (k = 2; k < flen; k++) {
        c = 0;

        for (i = 0; i < flen - k + 1; i++)
            c += add(b, buf + i, k, is);

        printf("%zd\n", c);
    }

    return 0;
}

Melhorias

1. 8 → 9: Leia o arquivo inteiro no início, pré-processe uma vez e mantenha-o no centro. Isso melhora muito a taxa de transferência.
2. Use menos memória, escreva a saída correta.
3. Corrija o formato de saída novamente.
4. Corrija off-by-one.
5. 9 → 10: Não jogue fora o que você já fez.