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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2021-2022 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
struct ZSearcher<Searched: Collection> {
let pattern: [Searched.Element]
let z: [Int]
let areEquivalent: (Searched.Element, Searched.Element) -> Bool
init(
pattern: [Searched.Element],
by areEquivalent: @escaping (Searched.Element, Searched.Element
) -> Bool) {
self.pattern = pattern
self.z = zAlgorithm(pattern, by: areEquivalent)
self.areEquivalent = areEquivalent
}
}
extension ZSearcher: StatelessCollectionSearcher {
func search(
_ searched: Searched,
in range: Range<Searched.Index>
) -> Range<Searched.Index>? {
var l = range.lowerBound
var r = l
var distanceFromL = 0
var distanceToR = 0
func compare(
start: Searched.Index,
end: Searched.Index,
minLength: Int
) -> Range<Searched.Index>? {
var left = minLength
var right = end
while left != pattern.endIndex
&& right != range.upperBound
&& areEquivalent(pattern[left], searched[right]) {
left += 1
searched.formIndex(after: &right)
}
if left == pattern.count {
return start..<right
} else {
l = start
r = right
distanceFromL = 0
distanceToR = left
return nil
}
}
var i = range.lowerBound
while true {
if i >= r {
if let range = compare(start: i, end: i, minLength: 0) {
return range
}
} else {
let length = distanceToR
let prev = z[distanceFromL]
if prev >= length {
if let range = compare(start: i, end: r, minLength: length) {
return range
}
}
}
if i == searched.endIndex {
return nil
}
searched.formIndex(after: &i)
distanceFromL += 1
distanceToR -= 1
}
}
}
func zAlgorithm<T>(_ elements: [T], by areEquivalent: (T, T) -> Bool) -> [Int] {
var z: [Int] = [elements.count]
z.reserveCapacity(elements.count)
var l = 0
var r = 0
func compare(start: Int, minLength: Int) {
var left = minLength
var right = start + minLength
while right < elements.count
&& areEquivalent(elements[left], elements[right])
{
left += 1
right += 1
}
z.append(left)
l = start
r = right
}
for index in elements.indices.dropFirst() {
if index >= r {
compare(start: index, minLength: 0)
} else {
let length = r - index
let prev = z[index - l]
if prev < length {
z.append(prev)
} else {
compare(start: index, minLength: length)
}
}
}
return z
}
|
