I'm having an optimization problem here. I would like to have this code running in O(n), which I tried for several hours now.

Byte-arrays c contains a string, e contains the same string, but sorted. Int-arrays nc and ne contain the indexes within the string, eg

```
c:
s l e e p i n g
nc:
0 0 0 1 0 0 0 0 
e:
e e g i l n p s
ne:
0 1 0 0 0 0 0 0

```

The problem now is that get\_next\_index is linear - is there a way to solve this?

```
void decode_block(int p) {
    BYTE xj = c[p];
    int nxj = nc[p];

    for (int i = 0; i < block_size; i++) {
        result[i] = xj;
        int q = get_next_index(xj, nxj, c, nc);
        xj = e[q];
        nxj = ne[q];
    }

    fwrite(result, sizeof (BYTE), block_size, stdout);
    fflush(stdout);
}

int get_next_index(BYTE xj, int nxj, BYTE* c, int* nc) {
    int i = 0;
    while ( ( xj != c[i] ) || ( nxj != nc[i] ) ) {
      i++;
    }
    return i;
}

```

This is part of an [Burrows-Wheeler](http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform) implementation

It starts with

```
xj = c[p]
nxj = nc[p]

```

Next I have to block\_size (= length c = length nc = length e = length ne) times

* store the result xj in result
* find the number index for which c[i] == xj
* xj is now e[i]

ne and nc are only used to make sure that every character in e and c is unique (e\_0 != e\_1).