-
Notifications
You must be signed in to change notification settings - Fork 576
/
last_index_of_needle.ts
49 lines (48 loc) · 1.42 KB
/
last_index_of_needle.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license.
// This module is browser compatible.
/** Returns the index of the last occurrence of the needle array in the source
* array, or -1 if it is not present.
*
* A start index can be specified as the third argument that begins the search
* at that given index. The start index defaults to the end of the array.
*
* The complexity of this function is O(source.lenth * needle.length).
*
* ```ts
* import { lastIndexOfNeedle } from "https://deno.land/std@$STD_VERSION/bytes/last_index_of_needle.ts";
* const source = new Uint8Array([0, 1, 2, 1, 2, 1, 2, 3]);
* const needle = new Uint8Array([1, 2]);
* console.log(lastIndexOfNeedle(source, needle)); // 5
* console.log(lastIndexOfNeedle(source, needle, 4)); // 3
* ```
*/
export function lastIndexOfNeedle(
source: Uint8Array,
needle: Uint8Array,
start = source.length - 1,
): number {
if (start < 0) {
return -1;
}
if (start >= source.length) {
start = source.length - 1;
}
const e = needle[needle.length - 1];
for (let i = start; i >= 0; i--) {
if (source[i] !== e) continue;
const pin = i;
let matched = 1;
let j = i;
while (matched < needle.length) {
j--;
if (source[j] !== needle[needle.length - 1 - (pin - j)]) {
break;
}
matched++;
}
if (matched === needle.length) {
return pin - needle.length + 1;
}
}
return -1;
}