# Finding position of a sequence in a UInt8 array?

**URL:** <https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757>\
**Category:** New to Julia\
**Created:** [August 29, 2020, 5:23pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757 "2020-08-29T17:23:23Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [August 29, 2020, 5:23pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/1 "2020-08-29T17:23:23Z")

</div>

Hello!

Suppose I have:

```julia
using Random
rand(MersenneTwister(0),UInt8,10)

10-element Array{UInt8,1}:
 0x40
 0x52
 0x99
 0x35
 0x90
 0xea
 0x00
 0x13
 0xdf
 0x18

```

Say I want to find the position of sequence “0x90 0xea 0x00”, how would I go about this?

Finding the position of “0x90” is not suitable, this is just a simplified example.

Kind regards

---

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [August 29, 2020, 5:30pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/2 "2020-08-29T17:30:32Z")

</div>

I have tried to use findfirst, skipchars etc. but only been able to use one char at a time currently

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [August 29, 2020, 5:57pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/3 "2020-08-29T17:57:40Z")

</div>

You can try the [KMP algorithm](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm).

---

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [August 29, 2020, 6:05pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/4 "2020-08-29T18:05:47Z")

</div>

Thanks for the suggestion, that might be what I have to do

Is what I am wanting “unreasonable” though? I thought that perhaps one would already be able to do this in native Julia

Kind regards

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [August 29, 2020, 6:22pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/5 "2020-08-29T18:22:44Z")

</div>

Certainly not unreasonable, just mostly used for strings.

A slightly perverse way is using `findfirst` with arrays converted to strings:

```julia
julia> a = String(UInt8[
       0x40
        0x52
        0x99
        0x35
        0x90
        0xea
        0x00
        0x13
        0xdf
        0x18
       ])
"@R\x995\x90\xea\0\x13\xdf\x18"

julia> findfirst(String(UInt8[0x90, 0xea, 0x00]), a)
5:7

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 29, 2020, 6:23pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/6 "2020-08-29T18:23:54Z")

</div>

> [@Ahmed\_Salih](#):
>
> Is what I am wanting “unreasonable” though? I thought that perhaps one would already be able to do this in native Julia

I think @Vasily_Pisarev was suggesting implementing KMP in native Julia. But probably what you really want is something that is already implemented.

As it turns out, searching for subsequences of byte arrays _is_ [already implemented in Julia `Base`](https://github.com/JuliaLang/julia/blob/3f7b556bb3b45cfcb2c718e3e5e0f1d912e4272d/base/strings/search.jl#L177-L236) in order to implement substring searching. You can call it via the undocumented function:

```julia
Base._searchindex(a, [0x90,0xea,0x00], 1)

```

to search for the starting index of the subsequence `0x90,0xea,0x00` in a byte array `a` starting at the beginning of the array, for example. It returns `0` if the subsequence was not found.

It might be [nice to add a high-level interface](https://github.com/JuliaLang/julia/issues/37280) for this via `findfirst` and `findnext` — should be a pretty easy PR since the main code is already implemented.

---

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [August 29, 2020, 7:51pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/7 "2020-08-29T19:51:43Z")

</div>

Thanks for the try, this was what I hoped to avoid, but of course I did not specify that in my question, so that was my fault

Kind regards

EDIT: Included a quote by mistake

---

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [August 29, 2020, 7:54pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/8 "2020-08-29T19:54:33Z")

</div>

This is so awesome thanks!

I just tested it for my purposes and before I was using ‘readuntil’ which allocated more and took longer time, so using this gave me a 10x improvement in timing (in my initial fast test).

I think your suggestions of making this more accessible is good and thanks for putting a PR up or what it is called 🙂

Lastly could you explain to me what the last “1” does in your example? I tried changing it, since I thought it would find an occurence two times if say it was “2” but I couldn’t figure it out. Maybe it is axis of search direction?

Kind regards

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 29, 2020, 8:15pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/9 "2020-08-29T20:15:54Z")

</div>

> [@Ahmed\_Salih](#):
>
> Lastly could you explain to me what the last “1” does in your example?

It’s the starting index for the search, the same as the [`start` argument of `findnext`](https://docs.julialang.org/en/latest/base/strings/#Base.findnext-Tuple%7BAbstractString,AbstractString,Integer%7D) — it says to search starting at byte `1`. Passing `2` means to search starting at byte `2`.

In this way, you can find multiple occurrences:

```julia
i = Base._searchindex(a, [0x90,0xea,0x00], 1)
Base._searchindex(a, [0x90,0xea,0x00], i+1) # finds the second occurrence, if any

```

---

<div class="post-metadata">

**Author:** ![Ahmed\_Salih](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ahmed_salih/32/206579_2.png) [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)\
**Post date:** [August 29, 2020, 8:26pm UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/10 "2020-08-29T20:26:11Z")

</div>

Makes total sense, thanks!

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 30, 2020, 1:01am UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/11 "2020-08-30T01:01:53Z")

</div>

> [@Ahmed\_Salih](#):
>
> thanks for putting a PR up or what it is called 🙂

I filed an [issue](https://github.com/JuliaLang/julia/issues/37280) suggesting the feature, but I didn’t create a [pull request (PR)](https://docs.github.com/en/github/collaborating-with-issues-and-pull-requests/about-pull-requests) — a PR occurs when someone actually implements the feature and requests for it to be merged.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [August 30, 2020, 2:18am UTC](https://discourse.julialang.org/t/finding-position-of-a-sequence-in-a-uint8-array/45757/12 "2020-08-30T02:18:44Z")

</div>

behold, there exists an actual [PR](https://github.com/JuliaLang/julia/pull/37283) now