Table of Contents
Algorithm
Leetcode 1092: Shortest Common Supersequence
https://dreamume.medium.com/leetcode-1092-shortest-common-supersequence-5aec2e6ed2da
Review
扩展添加新的功能到一个现存的类、结构、枚举或协议类型。这包括能力扩展你不能访问源代码类型的能力。扩展跟 Objective-C 里的类别相似（不同的是，Swift 扩展没有名字）
Swift 的扩展可以：
- 添加计算实例属性和计算类型属性
- 定义实例方法和类型方法
- 提供新的初始化
- 定义下标
- 定义和使用新的嵌套类型
- 使现存类型服从一个协议
在 Swift 中，你甚至可以扩展一个协议来提供它需要的实现或添加额外的功能
注意：扩展可添加新的功能到一个类型，但不能覆盖现有的功能
扩展语法
用 extension 关键字定义扩展
extension SomeType {
// new functionality to add to SomeType goes here
}
一个扩展可扩展一个现存的类型使它适配一个或多个协议。为添加服从的协议，跟类或结构一样写协议的名字
extension SomeType : SomeProtocol, AnotherProtocol {
// implementation of protocol requirements goes here
}
一个扩展可用来扩展一个现存的范型类型，你也可扩展一个范型类型来有条件地添加功能
计算属性
扩展可添加计算实例属性和计算类型属性到现存的类型。这个例子添加 5 个计算实例属性到 Swift 内建的 Double 类型，来提供距离单位支持
extension Double {
var km: Double { return self * 1_000.0 }
var m: Double { return self }
var cm: Double { return self / 100.0 }
var mm: Double { return self / 1_000.0 }
var ft: Double { return self / 3.28084 }
}
let oneInch = 25.4.mm
print("One inch is \(oneInch) meters")
let threeFeet = 3.ft
print("Three feet is \(threeFeet) meters")
let aMarathon = 42.km + 195.m
print("A marathon is \(aMarathon) meters long")
初始化
扩展可添加新的初始化方法到现存的类型。这使得你扩展其他类型来接受你自己自定义类型作为初始化参数，或提供额外的初始化选项
扩展可添加新的方便初始化方法到类，但它们不能添加新的设计初始化方法或析构方法到一个类
如果你使用一个扩展添加一个初始化方法到一个值类型，其提供缺省的值到它的所有存储属性且不定义任何自定义初始化方法，你可调用缺省初始化方法和值类型的成员初始化方法在你的扩展初始化方法中
如果你使用一个扩展添加一个初始化方法到一个结构，其定义在另一个模块，新的初始化方法不能访问 self 直到它从定义的模块中调用一个初始化方法
下面的例子定义一个自定义 Rect 结构来表达一个几何矩形。该例子也定义了两个支持结构称为 Size 和 Point，这两个都提供缺省值 0.0 作为所有它们的属性
struct Size {
var width = 0.0, height = 0.0
}
struct Point {
var x = 0.0, y = 0.0
}
struct Rect {
var origin = Point()
var size = Size()
}
因为 Rect 结构对它的所有属性提供缺省值，它自动有一个缺省初始化函数和一个成员初始化函数。这些初始化函数可被用来创建新的 Rect 实例
let defautRect = Rect()
let memberwiseRect = Rect(origin: Point(x: 2.0, y: 2.0),
size: Size(width: 5.0, height: 5.0))
你可扩展 Rect 结构来提供一个额外的初始化函数使用一个特别的中心点和大小：
extension Rect {
init(center: Point, size: Size) {
let originX = center.x - (size.width / 2)
let originY = center.y - (size.height / 2)
self.init(origin: Point(x: originX, y: originY), size:size)
}
}
注意：如果你用扩展提供一个新的初始化函数，你还是要保证每个实例在初始化函数之后是完全初始化的
方法
扩展可以添加新的实例方法和类方法到现有的类。下例添加了一个新的实例方法 repetitions 到 Int 类中:
extension Int {
func repetitions(task: () -> Void) {
for _ in 0..<self {
task()
}
}
}
可修改实例方法
扩展添加的实例方法也可以修改实例本身。结构和枚举方法修改本身或它的属性需要用关键字 mutating 标记实例方法
以下是一个例子
extension Int {
mutating func square() {
self = self * self;
}
}
var someInt = 3
someInt.square()
下标
扩展可添加新的下标到一个现存的类型。示例如下：
extension Int {
subscript(digitIndex: Int) -> Int {
var decimalBase = 1
for _ in 0..<digitIndex {
decimalBase *= 10
}
return (self / decimalBase) % 10
}
}
746381295[0] // 5
746381295[1] // 9
746381295[2] // 2
746381295[8] // 1
嵌套类型
扩展可添加新的嵌套类型到现存的类、结构和枚举：
extension Int {
enum Kind {
case negative, zero, positive
}
var kind: Kind {
switch self {
case 0:
return .zero
case let x where x > 0:
return .positive
default:
return .negative
}
}
}
这个例子中的嵌套枚举可用于任意 Int 值：
func printIntegerKinds(_ numbers: [Int]) {
for number in numbers {
case .negative:
print("-", terminator: "")
case .zero:
print("0 ", terminator: "")
case .positive:
print("+ ", terminator: "")
}
print("")
}
printIntegerKinds([3, 19, -27, 0, -6, 0, 7])
Tips
一个协议定义一系列方法、属性和其他需求满足一个特殊任务或功能片段。协议可被类、结构或枚举提供这些需求的实际实现来适配。任何满足协议需求的类型被称为服从该协议
协议语法
protocol SomeProtocol {
// protocol definition goes here
}
自定义类型在类型后面添加协议的名字来表述适配一个特殊的协议，通过逗号分隔，作为定义的一部分。可列举多个协议，用逗号分隔就行
struct SomeStructure: FirstProtocol, AnotherProtocol {
// structure definition goes here
}
属性需求
一个协议可要求任何服从类型提供一个实例属性或类属性。协议不指明属性为存储属性或计算属性 - 它只是指明需要属性的名字和类型。协议也指明是否每个属性必须是只读或读写
如果一个协议要求一个属性可读写，属性不能为常量存储属性或只读计算属性。如果协议只要求一个属性可读，则任意种类的属性都可
属性要求总是定义为变量属性，前面用 var 关键字。可读写属性用 { get set }，可读属性用 { get }
protocol SomeProtocol {
var mustBeSettable: Int { get set }
var doesNotNeedToBeSettable: Int { get }
}
声明类型属性时在最前面要加 static 关键字。对类的话用 class 或 static 关键字都可以
protocol AnotherProtocol {
static var someTypeProperty: Int { get set }
}
protocol FullyNamed {
var fullName: String { get }
}
struct Person: FullyNamed {
var fullName: String
}
let john = Person(fullName: "John Appleseed")
// john.fullName is "John Appleseed"
class Starship: FullyNamed {
var prefix: String?
var name: String
init(name: String, prefix: String? = nil) {
self.name = name
self.prefix = prefix
}
var fullName: String {
return (prefix != nil ? prefix! + " " : "") + name
}
}
var ncc1701 = Starship(name: "Enterprise", prefix: "USS")
// ncc1701.fullName is "USS Enterprise"
方法需求
协议可指明需求实例方法和类方法。
protocol SomeProtocol {
static func someTypeMethod()
}
protocol RandomNumberGenerator {
func random() -> Double
}
class LinearCongruentialGenerator: RandomNumberGenerator {
var lastRandom = 42.0
let m = 139968.0
let a = 3877.0
let c = 29573.0
func random() -> Double {
lastRandom = ((lastRandom * a + c)
.truncatingRemainder(dividingBy:m))
return lastRandom / m
}
}
let generator = LinearCongruentialGenerator()
print("Here's a random number: \(generator.random())")
// Prints "Here's a random number: 0.3746499199817101"
print("And another one: \(generator.random())")
// Prints "And another one: 0.729023776863283"
修改方法需求
注意：如果你用 mutating 关键字标注一个协议实例方法，在类中你不需要写 mutating 关键字到该方法实现，只有在结构和枚举中需要
protocol Togglable {
mutating func toggle()
}
enum OnOffSwitch: Togglable {
case off, on
mutating func toggle() {
switch self {
case .off:
self = .on
case .on:
self = .off
}
}
}
var lightSwitch = OnOffSwitch.off
lightSwitch.toggle()
// lightSwitch is now equal to .on
初始化函数需求
protocol SomeProtocol {
init(someParameter: Int)
}
class SomeClass: SomeProtocol {
required init(someParameter: Int) {
// initializer implementation goes here
}
}
注意：你不需要在标注 final 的类中加 required 关键字，因为 final 的类没有子类
如果一个子类从父类中覆盖一个设计初始化函数，也实现了协议需要的初始化函数，需要在函数前加 required 和 override 关键字
protocol SomeProtocol {
init()
}
class SomeSuperClass {
init() {
// initializer implementation goes here
}
}
class SomeSubClass: SomeSuperClass, SomeProtocol {
// "required" from SomeProtocol conformance; "override" from SomeSuperClass
required override init() {
// initializer implementation goes here
}
}
可失败初始化函数需求
协议中可定义可失败初始化函数需求
一个可失败初始化需求可被一个可失败或非可失败初始化函数满足。一个非可失败初始化函数需求可被一个非可失败初始化函数或一个间接解封可失败初始化函数满足
协议作为类型
最常见的方式是使用一个协议作为一个类型的范型限制。不透明类型可服从一个协议。封装协议类型服从协议。为支持运行时灵活性，Swift 在必要时添加了一个间接层 - 封装，其有一个性能成本。因为这个灵活性，Swift 在编译期不知道底层的类型，意味着你只能访问协议需求上的成员。访问任何底层类型的其他 API 需要在运行时强转
代理
代理是一种设计范型使得一个类或结构代理一些责任到另一个类型的一个实例。下面是一个例子：
class DiceGame {
let sides: Int
let generator = LinearCongruentialGenerator()
weak var delegate: Delegate?
init(sides: Int) {
self.sides = sides
}
func roll() -> Int {
return Int(generator.random() * Double(sides)) + 1
}
func play(rounds: Int) {
delegate?.gameDidStart(self)
for round in 1...rounds {
let player1 = roll()
let player2 = roll()
if player1 == player2 {
delegate?.game(self, didEndRound: round, winner: nil)
} else if player1 > player2 {
delegate?.game(self, didEndRound: round, winner: 1)
} else {
delegate?.game(self, didEndRound: round, winner: 2)
}
}
delegate?.gameDidEnd(self)
}
protocol Delegate: AnyObject {
func gameDidStart(_ game: DiceGame)
func game(_ game: DiceGame, didEndRound round: Int, winner: Int?)
func gameDidEnd(_ game: DiceGame)
}
}
class DiceGameTracker: DiceGame.Delegate {
var playerScore1 = 0
var playerScore2 = 0
func gameDidStart(_ game: DiceGame) {
print("Started a new game")
playerScore1 = 0
playerScore2 = 0
}
func game(_ game: DiceGame, didEndRound round: Int, winner: Int?) {
switch winner {
case 1:
playerScore1 += 1
print("Player 1 won round \(round)")
case 2: playerScore2 += 1
print("Player 2 won round \(round)")
default:
print("The round was a draw")
}
}
func gameDidEnd(_ game: DiceGame) {
if playerScore1 == playerScore2 {
print("The game ended in a draw.")
} else if playerScore1 > playerScore2 {
print("Player 1 won!")
} else {
print("Player 2 won!")
}
}
}
let tracker = DiceGameTracker()
let game = DiceGame(sides: 6)
game.delegate = tracker
game.play(rounds: 3)
// Started a new game
// Player 2 won round 1
// Player 2 won round 2
// Player 1 won round 3
// Player 2 won!
用一个扩展添加协议服从
你可扩展一个现存的类型来适配和服从一个新的协议，甚至你没有访问现存的饿代码的权限。示例如下
protocol TextRepresentable {
var textualDescription: String { get }
}
extension Dice: TextRepresentable {
var textualDescription: String {
return "A \(sides)-sided dice"
}
}
let d12 = Dice(sides: 12, generator: LinearCongruentialGenerator())
print(d12.textualDescription)
// Prints "A 12-sided dice"
extension SnakesAndLadders: TextRepresentable {
var textualDescription: String {
return "A game of Snakes and Ladders with \(finalSquare) squares"
}
}
print(game.textualDescription)
// Prints "A game of Snakes and Ladders with 25 squares"
有条件地服从一个协议
一个范型类型可能只在某种条件下满足协议需求，比如当类型的范型参数服从协议时。你可使一个范型类型有条件地服从一个协议通过列举限制来扩展类型。如下是一个例子：
extension Array: TextRepresentable where Element: TextRepresentable {
var textualDescription: String {
let itemsAsText = self.map { $0.textualDescription }
return "[" + itemsAsText.joined(separator: ", ") + "]"
}
}
let myDice = [d6, d12]
print(myDice.textualDescription)
// Prints "[A 6-sided dice, A 12-sided dice]"
用扩展定义协议适配
如果一个类型已经服从所有协议需求，但还没有表明它适配该协议，你可使它用一个空的扩展适配该协议
struct Hamster {
var name: String
var textualDescription: String {
return "A hamster named \(name)"
}
}
extension Hamster: TextRepresentable {}
let simonTheHamster = Hamster(name: "Simon")
let somethingTextRepresentable: TextRepresentable = simonTheHamster
print(somethingTextRepresentable.textualDescription)
// Prints "A hamster named Simon"
使用一个综合实现适配一个协议
Swift 在许多简单例子中可自动提供 Equatable、Hashable 和 Comparable 协议的服从。使用这种综合实现意味着你不需要写重复的代码实现协议需求
Swift 对如下自定义类型提供一个 Equatable 综合实现
- 只有存储属性的结构服从 Equatable 协议
- 只有相关类型的枚举服从 Equatable 协议
- 枚举没有相关类型
为接收一个 = 的综合实现，在包含原始定义的文件里定义服从 Equatable，不需要自己实现一个 = 操作符。Equatable 协议提供一个缺省的 != 实现，以下是一个例子
struct Vector3D: Equatable {
var x = 0.0, y = 0.0, z = 0.0
}
let twoThreeFour = Vector3D(x: 2.0, y: 3.0, z: 4.0)
let anotherTwoThreeFour = Vector3D(x: 2.0, y: 3.0, z: 4.0)
if twoThreeFour == anotherTwoThreeFour {
print("These two vectors are also equivalent.")
}
// Prints "These two vectors are also equivalent."
Swift 对如下自定义类型提供一个 Hashable 的综合实现
- 只有存储属性的结构服从 Hashable 协议
- 只有相关类型的枚举服从 Hashable 协议
- 没有相关类型的枚举
为接收 hash(into:) 的一个综合实现，在包含原始定义的文件里定义服从 Hashable 协议，不需要实现 hash(into:) 方法本身
Swift 对没有原始值的枚举提供 Comparable 的一个综合实现。如果枚举有相关类型，它们必须都服从 Comparable 协议。为接收一个 < 的综合实现，在原始枚举定义的文件里定义服从 Comparable 协议，不需要实现 < 操作符本身。Comparable 协议缺省实现 <=、> 和 >= 操作符
enum SkillLevel: Comparable {
case beginner
case intermediate
case expert(stars: Int)
}
var levels = [SkillLevel.intermediate, SkillLevel.beginner,
SkillLevel.expert(stars: 5), SkillLevel.expert(stars: 3)]
for level in levels.sorted() {
print(level)
}
// Prints "beginner"
// Prints "intermediate"
// Prints "expert(stars: 3)"
// Prints "expert(stars: 5)"
协议类型的聚合
一个协议可被用来作为一个类型存储在聚合类型比如一个数组或一个字典。例子如下：
let things: [TextRepresentable] = [game, d12, simonTheHamster]
for thing in things {
print(thing.textualDescription)
}
// A game of Snakes and Ladders with 25 squares
// A 12-sided dice
// A hamster named Simon
协议继承
一个协议可继承一个或多个其他协议且添加进一步的需求，示例如下
protocol InheritingProtocol: SomeProtocol, AnotherProtocol {
// protocol definition goes here
}
protocol PrettyTextRepresentable: TextRepresentable {
var prettyTextualDescription: String { get }
}
extension SnakesAndLadders: PrettyTextRepresentable {
var prettyTextualDescription: String {
var output = textualDescription + ":\n"
for index in 1...finalSquare {
switch board[index] {
case let ladder where ladder > 0:
output += "▲ "
case let snake where snake < 0:
output += "▼ "
default:
output += "○ "
}
}
return output
}
}
只适合类的协议
你可通过添加 AnyObject 协议到协议继承列表来限制协议适配类类型
protocol SomeClassOnlyProtocol: AnyObject, SomeInheritedProtocol {
// class-only protocol definition goes here
}
协议组合
要求一个类型服从多个协议是很有用的，协议组合形式如： SomeProtocol & AnotherProtocol。下面是一个例子：
protocol Named {
var name: String { get }
}
protocol Aged {
var age: Int { get }
}
struct Person: Named, Aged {
var name: String
var age: Int
}
func wishHappyBirthday(to celebrator: Named & Aged) {
print("Happy birthday, \(celebrator.name), you're \(celebrator.age)!")
}
let birthdayPerson = Person(name: "Malcolm", age: 21)
wishHappyBirthday(to: birthdayPerson)
// Prints "Happy birthday, Malcolm, you're 21!"
另一个例子：
class Location {
var latitude: Double
var longitude: Double
init(latitude: Double, longitude: Double) {
self.latitude = latitude
self.longitude = longitude
}
}
class City: Location, Named {
var name: String
init(name: String, latitude: Double, longitude: Double) {
self.name = name
super.init(latitude: latitude, longitude: longitude)
}
}
func beginConcert(in location: Location & Named) {
print("Hello, \(location.name)!")
}
let seattle = City(name: "Seattle", latitude: 47.6, longitude: -122.3)
beginConcert(in: seattle)
// Prints "Hello, Seattle!"
协议服从的检查
你可使用 is 和 as 关键字检查协议服从情况，且转换到一个特别的协议类型：
- is 操作符返回 true 如果一个实例服从一个协议，否则返回 false
- as? 版本返回一个协议类型的可选值，如果实例不服从协议则返回 nil
-
as! 版本返回一个协议类型，如果不成功则触发一个运行时错误
protocol HasArea { var area: Double { get } }
class Circle: HasArea { let pi = 3.1415927 var radius: Double var area: Double { return pi * radius * radius } init(radius: Double) { self.radius = radius } } class Country: HasArea { var area: Double init(area: Double) { self.area = area } }
class Animal { var legs: Int init(legs: Int) { self.legs = legs } }
let objects: [AnyObject] = [ Circle(radius: 2.0), Country(area: 243_610), Animal(legs: 4) ]
for object in objects { if let objectWithArea = object as? HasArea { print(“Area is (objectWithArea.area)”) } else { print(“Something that doesn’t have an area”) } } // Area is 12.5663708 // Area is 243610.0 // Something that doesn’t have an area
可选协议需求
你可对协议定义可选需求。这些需求不需要服从协议的类型实现。可选需求需要添加 optional 关键字。协议和可选需求必须用 @objc 属性标注。注意 @objc 协议只能适配于类，不能是结构或枚举
当你在可选需求中使用一个方法或属性，它的类型自动变成可选的。例如，一个方法 (Int) -> String 变成 ((Int) -> String)?。注意整个函数类型封装在可选里，而不是函数的返回值
一个可选协议需求可被可选链调用。示例如下：
@objc protocol CounterDataSource {
@objc optional func increment(forCount count: Int) -> Int
@objc optional var fixedIncrement: Int { get }
}
class Counter {
var count = 0
var dataSource: CounterDataSource?
func increment() {
if let amount = dataSource?.increment?(forCount: count) {
count += amount
} else if let amount = dataSource?.fixedIncrement {
count += amount
}
}
}
class ThreeSource: NSObject, CounterDataSource {
let fixedIncrement = 3
}
var counter = Counter()
counter.dataSource = ThreeSource()
for _ in 1...4 {
counter.increment()
print(counter.count)
}
// 3
// 6
// 9
// 12
class TowardsZeroSource: NSObject, CounterDataSource {
func increment(forCount count: Int) -> Int {
if count == 0 {
return 0
} else if count < 0 {
return 1
} else {
return -1
}
}
}
counter.count = -4
counter.dataSource = TowardsZeroSource()
for _ in 1...5 {
counter.increment()
print(counter.count)
}
// -3
// -2
// -1
// 0
// 0
协议扩展
协议可扩展来提供方法、初始化函数、下标和计算属性实现来服从类型。例如，RandomNumberGenerator 协议可扩展来提供一个 randomBool() 函数：
extension RandomNumberGenerator {
func randomBool() -> Bool {
return random() > 0.5
}
}
let generator = LinearCongruentialGenerator()
print("Here's a random number: \(generator.random())")
// Prints "Here's a random number: 0.3746499199817101"
print("And here's a random Boolean: \(generator.randomBool())")
// Prints "And here's a random Boolean: true"
提供缺省实现
你可使用协议扩展来提供一个缺省实现到任意方法或计算属性。如果一个服从类型提供它自己的实现，该实现将被使用而不是扩展中的实现
extension PrettyTextRepresentable {
var prettyTextualDescription: String {
return textualDescription
}
}
添加限制到协议扩展
当你定义一个协议扩展，你可指定服从类型必须满足的限制。示例如下：
extension Collection where Element: Equatable {
func allEqual() -> Bool {
for element in self {
if element != self.first {
return false
}
}
return true
}
}
let equalNumbers = [100, 100, 100, 100, 100]
let differentNumbers = [100, 100, 200, 100, 200]
print(equalNumbers.allEqual())
// Prints "true"
print(differentNumbers.allEqual())
// Prints "false"
如果一个服从类型满足对相同方法或属性的多个限制扩展实现需求，Swift 使用最强的限制实现
Share
Boyer-Moore majority vote algorithm
Boyer-Moore 大多数投票算法是使用线性时间和常量内存找到序列中多数元素的算法。它因 Robert S.Boyer 和 J Strother Moore 命名，发布于 1981 年，是流式算法的一个原型例子
在它最简单的形式中，算法找到一个多数元素，如存在的话：一个元素出现次数超过输入元素的一半。算法的一个版本是数据可被用于第二阶段验证在第一阶段发现的元素是否是一个多数元素
如果第二阶段没有执行且没有多数元素，算法不会检测出没有多数元素存在。在没有多数元素存在的情况下，返回的元素可为任意。它不保障元素是最多的。对一个流算法不可能在小于线性空间的条件下找到最频繁的元素，对序列数的重复数可很小
描述
算法用本地变量维护一个序列元素和一个统计，统计变量初始化为 0。然后处理序列元素，一次一个。当处理元素 x 时，如果统计为 0，算法存储 x 作为它的记忆序列元素且设置统计为 1。否则，它比较 x 和存储的元素且要么增加统计（如果它们相等）或减少统计（否则）。这个处理的最后，如果序列有一个多数元素，它将为算法存储的元素。这个表达用伪码表示如下：
- 初始化一个元素 m 和一个统计变量 c = 0
- 对输入序列的每个元素 x：
- 如果 c = 0，则赋值 m = x 且 c = 1
- 如果 m = x，则 c = c + 1
- 否则赋值 c = c - 1
- 返回 m
即使输入没有多数元素，算法将报道一个序列元素作为结果。然而，它可能在相同的输入序列中执行第二阶段来统计该元素是否是多数元素。这个第二阶段是需要的，因为它不可能对子线性空间算法决定是否存在一个多数元素在一个阶段中
分析
算法需要的内存是一个元素和一个统计值的空间。在计算随机访问模型中通常用来作为算法分析，这些值的每个可被存储在一个机器字节且总空间为 O(1)。如果一个数组索引需要跟踪在输入序列中的算法位置，它不改变总的常量空间边界。算法的位复杂度（它需要的空间，例如，在一个图灵机上）更高
相似地，在一个随机访问机器算法要花费 O(n) 在 n 个元素的输入序列上，因为它对每个输入项目只执行一个常量时间的操作。算法也能被实现在一个图灵机以线性时间在输入长度上
正确性
假设输入包含一个多数元素 x，其重复次数超过输入长度的一半。则算法应该返回 x 作为最后的值 m。Boyer 和 Moore 证明如下更强的陈述：对算法最后的值 m 和 c，在一个长度为 n 的序列上，它总是可能分区输入值为 m 的 c 次和 (n - c)/2 对不等项目。因没有元素 x != m 有多数，因为 x 有至少半数元素在不等对和非 m 的 c 次拷贝。这样，如果有一个多数元素，它只能为 m
为证明这个分区的存在，Boyer 和 Moore 通过在输入序列长度上归纳处理。在每个步骤，它们使用归纳假设来找到最后删除元素的输入序列相同类型的分区，用 m 值。如果最后的输入值也是 m，它增加 m 的重复次数 c。如果它不等于 m，且 c 为正，则 c 次数从集合中移除一个。如果 c 为 0，则最终值可被添加到 m 的集合中，即使这个步骤导致 m 改变。这样，在所有的情况中，Boyer 和 Moore 描述的分区继续存在