1// The strstr implementation in this file is extracted from the Rust standard
2// library's str::find. The algorithm works for arbitrary &[T] haystack and
3// needle but is only exposed by the standard library on UTF-8 strings.
4//
5// https://github.com/rust-lang/rust/blob/1.40.0/src/libcore/str/pattern.rs
6//
7// ---
8//
9// This is the Two-Way search algorithm, which was introduced in the paper:
10// Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
11//
12// Here's some background information.
13//
14// A *word* is a string of symbols. The *length* of a word should be a familiar
15// notion, and here we denote it for any word x by |x|. (We also allow for the
16// possibility of the *empty word*, a word of length zero.)
17//
18// If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be
19// a *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] ==
20// x[i+p]. For example, both 1 and 2 are periods for the string "aa". As another
21// example, the only period of the string "abcd" is 4.
22//
23// We denote by period(x) the *smallest* period of x (provided that x is
24// non-empty). This is always well-defined since every non-empty word x has at
25// least one period, |x|. We sometimes call this *the period* of x.
26//
27// If u, v and x are words such that x = uv, where uv is the concatenation of u
28// and v, then we say that (u, v) is a *factorization* of x.
29//
30// Let (u, v) be a factorization for a word x. Then if w is a non-empty word
31// such that both of the following hold
32//
33// - either w is a suffix of u or u is a suffix of w
34// - either w is a prefix of v or v is a prefix of w
35//
36// then w is said to be a *repetition* for the factorization (u, v).
37//
38// Just to unpack this, there are four possibilities here. Let w = "abc". Then
39// we might have:
40//
41// - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
42// - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
43// - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
44// - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
45//
46// Note that the word vu is a repetition for any factorization (u,v) of x = uv,
47// so every factorization has at least one repetition.
48//
49// If x is a string and (u, v) is a factorization for x, then a *local period*
50// for (u, v) is an integer r such that there is some word w such that |w| = r
51// and w is a repetition for (u, v).
52//
53// We denote by local_period(u, v) the smallest local period of (u, v). We
54// sometimes call this *the local period* of (u, v). Provided that x = uv is
55// non-empty, this is well-defined (because each non-empty word has at least one
56// factorization, as noted above).
57//
58// It can be proven that the following is an equivalent definition of a local
59// period for a factorization (u, v): any positive integer r such that x[i] ==
60// x[i+r] for all i such that |u| - r <= i <= |u| - 1 and such that both x[i]
61// and x[i+r] are defined. (i.e., i > 0 and i + r < |x|).
62//
63// Using the above reformulation, it is easy to prove that
64//
65// 1 <= local_period(u, v) <= period(uv)
66//
67// A factorization (u, v) of x such that local_period(u,v) = period(x) is called
68// a *critical factorization*.
69//
70// The algorithm hinges on the following theorem, which is stated without proof:
71//
72// **Critical Factorization Theorem** Any word x has at least one critical
73// factorization (u, v) such that |u| < period(x).
74//
75// The purpose of maximal_suffix is to find such a critical factorization.
76//
77// If the period is short, compute another factorization x = u' v' to use for
78// reverse search, chosen instead so that |v'| < period(x).
79
80use std::cmp;
81use std::usize;
82
83pub fn find(haystack: &[char], needle: &[char]) -> Option<usize> {
84 assert!(!needle.is_empty());
85
86 // crit_pos: critical factorization index
87 let (crit_pos_false, period_false) = maximal_suffix(needle, false);
88 let (crit_pos_true, period_true) = maximal_suffix(needle, true);
89 let (crit_pos, mut period) = if crit_pos_false > crit_pos_true {
90 (crit_pos_false, period_false)
91 } else {
92 (crit_pos_true, period_true)
93 };
94
95 // Byteset is an extension (not part of the two way algorithm); it is a
96 // 64-bit "fingerprint" where each set bit j corresponds to a (byte & 63) ==
97 // j present in the needle.
98 let byteset;
99 // Index into needle before which we have already matched.
100 let mut memory;
101
102 // A particularly readable explanation of what's going on here can be found
103 // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
104 // see the code for "Algorithm CP" on p. 323.
105 //
106 // What's going on is we have some critical factorization (u, v) of the
107 // needle, and we want to determine whether u is a suffix of &v[..period].
108 // If it is, we use "Algorithm CP1". Otherwise we use "Algorithm CP2", which
109 // is optimized for when the period of the needle is large.
110 let long_period = needle[..crit_pos] != needle[period..period + crit_pos];
111 if long_period {
112 // Long period case -- we have an approximation to the actual period,
113 // and don't use memorization.
114 //
115 // Approximate the period by lower bound max(|u|, |v|) + 1.
116 period = cmp::max(crit_pos, needle.len() - crit_pos) + 1;
117 byteset = byteset_create(needle);
118 // Dummy value to signify that the period is long.
119 memory = usize::MAX;
120 } else {
121 // Short period case -- the period is exact.
122 byteset = byteset_create(&needle[..period]);
123 memory = 0;
124 }
125
126 // One of the main ideas of Two-Way is that we factorize the needle into two
127 // halves, (u, v), and begin trying to find v in the haystack by scanning
128 // left to right. If v matches, we try to match u by scanning right to left.
129 // How far we can jump when we encounter a mismatch is all based on the fact
130 // that (u, v) is a critical factorization for the needle.
131 let mut position = 0;
132 let needle_last = needle.len() - 1;
133 'search: loop {
134 // Check that we have room to search in. position + needle_last cannot
135 // overflow if we assume slices are bounded by isize's range.
136 let tail_byte = *haystack.get(position + needle_last)?;
137
138 // Quickly skip by large portions unrelated to our substring.
139 if !byteset_contains(byteset, tail_byte) {
140 position += needle.len();
141 if !long_period {
142 memory = 0;
143 }
144 continue 'search;
145 }
146
147 // See if the right part of the needle matches.
148 let start = if long_period {
149 crit_pos
150 } else {
151 cmp::max(crit_pos, memory)
152 };
153 for i in start..needle.len() {
154 if needle[i] != haystack[position + i] {
155 position += i - crit_pos + 1;
156 if !long_period {
157 memory = 0;
158 }
159 continue 'search;
160 }
161 }
162
163 // See if the left part of the needle matches.
164 let start = if long_period { 0 } else { memory };
165 for i in (start..crit_pos).rev() {
166 if needle[i] != haystack[position + i] {
167 position += period;
168 if !long_period {
169 memory = needle.len() - period;
170 }
171 continue 'search;
172 }
173 }
174
175 // We have found a match!
176 return Some(position);
177 }
178}
179
180fn byteset_create(chars: &[char]) -> u64 {
181 chars.iter().fold(init:0, |a: u64, &ch: char| (1 << (ch as u8 & 0x3f)) | a)
182}
183
184fn byteset_contains(byteset: u64, ch: char) -> bool {
185 (byteset >> ((ch as u8 & 0x3f) as usize)) & 1 != 0
186}
187
188// Compute the maximal suffix of `arr`.
189//
190// The maximal suffix is a possible critical factorization (u, v) of `arr`.
191//
192// Returns (`i`, `p`) where `i` is the starting index of v and `p` is the
193// period of v.
194//
195// `order_greater` determines if lexical order is `<` or `>`. Both
196// orders must be computed -- the ordering with the largest `i` gives
197// a critical factorization.
198//
199// For long period cases, the resulting period is not exact (it is too short).
200fn maximal_suffix(arr: &[char], order_greater: bool) -> (usize, usize) {
201 let mut left = 0; // Corresponds to i in the paper
202 let mut right = 1; // Corresponds to j in the paper
203 let mut offset = 0; // Corresponds to k in the paper, but starting at 0
204 // to match 0-based indexing.
205 let mut period = 1; // Corresponds to p in the paper
206
207 while let Some(&a) = arr.get(right + offset) {
208 // `left` will be inbounds when `right` is.
209 let b = arr[left + offset];
210 if (a < b && !order_greater) || (a > b && order_greater) {
211 // Suffix is smaller, period is entire prefix so far.
212 right += offset + 1;
213 offset = 0;
214 period = right - left;
215 } else if a == b {
216 // Advance through repetition of the current period.
217 if offset + 1 == period {
218 right += offset + 1;
219 offset = 0;
220 } else {
221 offset += 1;
222 }
223 } else {
224 // Suffix is larger, start over from current location.
225 left = right;
226 right += 1;
227 offset = 0;
228 period = 1;
229 }
230 }
231 (left, period)
232}
233