Debian Codegraph @

bytes/two_way.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 use types;
5
6 // Implements the so called Two-way string matching algorithm by Crochemore and
7 // Perrin. It pre-processes the needle in O(len(needle)) steps and performs the
8 // matching in O(len(haystack)) steps. It does so without any space overhead.
9 fn index_tw(haystack: []u8, needle: []u8) (size | void) = {
10 const n = len(haystack);
11 const m = len(needle);
12 if (n < m) {
13 return void;
14 };
15 if (n == m) {
16 return if (equal(haystack, needle)) 0 else void;
17 };
18
19 // pre-processing
20 let tup1 = max_suf(needle, false);
21 let i = tup1.0, p = tup1.1;
22 let tup2 = max_suf(needle, true);
23 let j = tup2.0, q = tup2.1;
24 let ms = i;
25 let per = p;
26 if (i + 1 < j + 1) {
27 ms = j;
28 per = q;
29 };
30
31 let mem0 = 0z, mem = 0z;
32 if (equal(haystack[..ms + 1], haystack[per..per + ms + 1])) {
33 if (ms + 1 > m - ms - 1) {
34 per = ms + 2;
35 } else {
36 per = m - ms;
37 };
38 mem0 = m - per;
39 };
40
41
42 j = 0;
43 for (j <= n - m) {
44 // right half
45 i = if (ms + 1 > mem) ms + 1 else mem;
46 for (i < m && needle[i] == haystack[j + i]) {
47 i += 1;
48 };
49 if (i < m) {
50 j += i - ms;
51 mem = 0;
52 continue;
53 };
54
55 // left half
56 i = ms + 1;
57 for (i > mem && needle[i - 1] == haystack[j + i - 1]) {
58 i -= 1;
59 };
60 if (i <= mem) {
61 return j;
62 };
63 j += per;
64 mem = mem0;
65 };
66 };
67
68 fn max_suf(x: []u8, inv: bool) (size, size) = {
69 let i = types::SIZE_MAX;
70 let j = 0z;
71 let k = 1z, p = 1z;
72 let m = len(x);
73 for (j + k < m) {
74 let a = x[j + k];
75 let b = x[i + k];
76 if (a == b) {
77 if (k == p) {
78 j += p;
79 k = 1;
80 } else {
81 k += 1;
82 };
83 } else if (a < b ^^ inv) {
84 j += k;
85 k = 1;
86 p = j - i;
87 } else {
88 i = j;
89 j += 1;
90 k = 1;
91 p = 1;
92 };
93 };
94 return (i, p);
95 };