string - 在字符串中查找搜索词的所有索引

Question

我需要一种快速方法来查找字符串中可能出现的搜索词的所有索引。我尝试了这种“蛮力”String 扩展方法:

// Note: makes use of ExSwift
extension String
{
    var length: Int { return count(self) }

    func indicesOf(searchTerm:String) -> [Int] {
        var indices = [Int]()
        for i in 0 ..< self.length {
            let segment = self[i ... (i + searchTerm.length - 1)]
            if (segment == searchTerm) {
                indices.append(i)
            }
        }
        return indices;
    }
}

...但是速度慢得离谱，尤其是搜索词越短。快速查找所有索引的更好方法是什么？

Answer 1

正如 Martin 所说，您可以在字符串匹配中实现一些众所周知的最快算法，Knuth–Morris–Pratt字符串搜索算法(或 KMP 算法)在主“文本字符串”S 中搜索“单词”W 的出现。

算法有复杂度O(n) ，其中 n 是 S 的长度，O 是 big-O notation .

extension String {

    // Build pi function of prefixes
    private func build_pi(str: String) -> [Int] {

       var n = count(str)
       var pi = Array(count: n + 1, repeatedValue: 0)
       var k = -1
       pi[0] = -1

       for (var i = 0; i < n; ++i) {
           while (k >= 0 && str[k] != str[i]) {
              k = pi[k]
           }
           pi[i + 1] = ++k
       }

       return pi
    }

    // Knuth-Morris Pratt algorithm
    func searchPattern(pattern: String) -> [Int] {

       var matches = [Int]()
       var n = count(self)

       var m = count(pattern)
       var k = 0
       var pi = build_pi(pattern)

       for var i = 0; i < n; ++i {
           while (k >= 0 && (k == m || pattern[k] != self[i])) {
              k = pi[k]
           }
           if ++k == m {
              matches.append(i - m + 1)
           }
       }

       return matches
    }

    subscript (i: Int) -> Character {
        return self[advance(self.startIndex, i)]
    }
}

那么您可以通过以下方式使用它:

var string = "apurba mandal loves ayoshi loves"
var pattern = "loves"

println(string.searchPattern(pattern))

输出应该是:

[14, 27]

属于字符串内模式出现的起始索引。希望对您有所帮助。

EDIT:

正如 Martin 在他的评论中所说，您需要避免使用 advance 函数通过 Int 索引 String 因为它是 < em>O(索引位置)。

一个可能的解决方案是将 String 转换为 Character 数组，然后访问索引是 O(1)。

那么extension可以改成这个:

extension String {

   // Build pi function of prefixes
   private func build_pi(str: [Character]) -> [Int] {

      var n = count(str)
      var pi = Array(count: n + 1, repeatedValue: 0)
      var k = -1
      pi[0] = -1

      for (var i = 0; i < n; ++i) {
          while (k >= 0 && str[k] != str[i]) {
              k = pi[k]
          }
          pi[i + 1] = ++k
      }

      return pi
   }

   // Knuth-Morris Pratt algorithm
   func searchPattern(pattern: String) -> [Int] {

      // Convert to Character array to index in O(1)
      var patt = Array(pattern)
      var S = Array(self)

      var matches = [Int]()
      var n = count(self)

      var m = count(pattern)
      var k = 0
      var pi = build_pi(patt)

      for var i = 0; i < n; ++i {
         while (k >= 0 && (k == m || patt[k] != S[i])) {
             k = pi[k]
         }
         if ++k == m {
             matches.append(i - m + 1)
         }
      }

      return matches
   }
}