28. 找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标

Show Swift Code

func computePMT(_ pattern: String) -> [Int] {  
    let m = pattern.length  
    var pmt = [Int](repeating: 0, count: m)  
    var j = 0  
      
    for i in 1..<m {  
        while j > 0 && pattern[pattern.index(pattern.startIndex, offsetBy: j)] != pattern[pattern.index(pattern.startIndex, offsetBy: i)] {  
            j = pmt[j - 1]  
        }  
        if pattern[pattern.index(pattern.startIndex, offsetBy: i)] == pattern[pattern.index(pattern.startIndex, offsetBy: j)] {  
            j += 1  
        }  
        pmt[i] = j  
    }  
    return pmt  
}  
  
func KMPSearch(_ haystack: String, _ needle: String) -> Int {  
    guard !needle.isEmpty else { return 0 } // 空字符串在所有位置都匹配  
      
    let n = haystack.length  
    let m = needle.length  
    let pmt = computePMT(needle)  
      
    var i = 0 // haystack的索引  
    var j = 0 // needle的索引  
      
    while i < n {  
        if haystack[haystack.index(haystack.startIndex, offsetBy: i)] == needle[needle.index(needle.startIndex, offsetBy: j)] {  
            // 字符匹配，继续比较下一个字符  
            i += 1  
            j += 1  
        } else if j > 0 {  
            // 字符不匹配，且j不是0，则利用pmt回溯  
            j = pmt[j - 1]  
        } else {  
            // 字符不匹配，且j是0，移动haystack的索引  
            i += 1  
        }  
          
        // 如果needle完全匹配，返回haystack中的起始索引  
        if j == m {  
            return i - m  
        }  
    }  
      
    // 没有找到匹配项  
    return -1  
}  
  
// 示例用法  
let haystack = "hello world"  
let needle = "world"  
let index = KMPSearch(haystack, needle)  
print(index) // 输出: 6  
  
let needle2 = "python"  
let index2 = KMPSearch(haystack, needle2)  
print(index2) // 输出: -1
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

这个 Swift 代码示例中，computePMT 函数用于计算部分匹配表（PMT），而 KMPSearch 函数则利用 PMT 来在 haystack 中搜索 needle。如果找到了 needle，函数返回它在 haystack 中的起始索引（从 0 开始）；如果没有找到，则返回 -1。

computePMT(_ pattern: String) -> [Int] 的参数和返回值, 怎么理解 ?

computePMT(_ pattern: String) -> [Int] 是一个 Swift 函数的声明，用于计算给定模式字符串（pattern）的部分匹配表（Partial Match Table，简称 PMT）。我们可以从以下几个方面来理解这个函数的参数和返回值：

参数

• _ pattern: String：这是函数的唯一参数，名为 pattern，类型为 String。前面的下划线 _ 是一种 Swift 中的命名约定，表示该参数在函数调用时可以省略其名称（即使用位置参数）。但在实际编程中，为了代码的可读性，通常还是推荐为参数命名。

返回值

• -> [Int]：这表示函数返回一个整数数组（Array<Int>）。这个数组就是部分匹配表（PMT），它记录了模式字符串中每个位置之前的子串的最长相同前后缀的长度。

如何理解部分匹配表（PMT）

部分匹配表（PMT）是 KMP（Knuth-Morris-Pratt）字符串匹配算法中的一个关键组件。KMP 算法利用 PMT 来避免在字符串匹配过程中不必要的字符比较，从而提高算法的效率。

PMT 的构建基于以下观察：

• 如果模式字符串的某个前缀（不包括整个字符串本身）存在相同的前后缀，那么当这个前缀在主字符串中不匹配时，我们可以将模式字符串向右滑动这个相同前后缀的长度，而不是仅仅滑动一个字符。

例如，对于模式字符串 "ABCDABD"：

• 前缀 "A" 没有相同的前后缀（除了空串），所以 PMT 的第一个元素是 0。
• 前缀 "AB" 没有相同的前后缀（除了空串），所以 PMT 的第二个元素是 0。
• 前缀 "ABC" 没有相同的前后缀（除了空串），所以 PMT 的第三个元素是 0。
• 前缀 "ABCD" 没有相同的前后缀（除了空串），所以 PMT 的第四个元素是 0。
• 前缀 "ABCDA" 的相同前后缀是 "A"，长度为 1，所以 PMT 的第五个元素是 1。
• 前缀 "ABCDAB" 的相同前后缀是 "AB"，长度为 2，所以 PMT 的第六个元素是 2。
• 前缀 "ABCDABD" 的相同前后缀是 "ABD"，长度为 3（注意不是 "AB"，因为我们要找的是最长的相同前后缀），所以 PMT 的第七个元素是 3。

因此，对于模式字符串 "ABCDABD"，其 PMT 为 [0, 0, 0, 0, 1, 2, 3]。这个 PMT 将在 KMP 算法中用于加速字符串匹配过程。