跳转至

字符串匹配

本頁面將簡述字符串匹配問題以及它的解法。

字符串匹配問題

定義

又稱模式匹配（pattern matching）。該問題可以概括為「給定字符串 \(S\) 和 \(T\)，在主串 \(S\) 中尋找子串 \(T\)」。字符 \(T\) 稱為模式串 (pattern)。

類型

  • 單串匹配：給定一個模式串和一個待匹配串，找出前者在後者中的所有位置。
  • 多串匹配：給定多個模式串和一個待匹配串，找出這些模式串在後者中的所有位置。
    • 出現多個待匹配串時，將它們直接連起來便可作為一個待匹配串處理。
    • 可以直接當做單串匹配，但是效率不夠高。
  • 其他類型：例如匹配一個串的任意後綴，匹配多個串的任意後綴……

暴力做法

簡稱 BF (Brute Force) 算法。該算法的基本思想是從主串 \(S\) 的第一個字符開始和模式串 \(T\) 的第一個字符進行比較，若相等，則繼續比較二者的後續字符；否則，模式串 \(T\) 回退到第一個字符，重新和主串 \(S\) 的第二個字符進行比較。如此往復，直到 \(S\) 或 \(T\) 中所有字符比較完畢。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/*
 * s：待匹配的主串
 * t：模式串
 * n：主串的長度
 * m：模式串的長度
 */
std::vector<int> match(char *s, char *t, int n, int m) {
  std::vector<int> ans;
  int i, j;
  for (i = 0; i < n - m + 1; i++) {
    for (j = 0; j < m; j++) {
      if (s[i + j] != t[j]) break;
    }
    if (j == m) ans.push_back(i);
  }
  return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def match(s, t, n, m):
    if m < 1:
        return []

    ans = []
    for i in range(0, n - m + 1):
        for j in range(0, m):
            if s[i + j] != t[j]:
                break
        else:
            ans.append(i)
    return ans

時間複雜度

設 \(n\) 為主串的長度，\(m\) 為模式串的長度。默認 \(m\ll n\)。

BF 算法匹配成功時，在最好情況下，只有一趟匹配成功，此趟比較次數為 \(m\)，而其餘每趟不成功的匹配都發生在模式串的第一個字符，還需要 \(n-m\) 次比較，總比較次數為 \(n\)，故時間複雜度為 \(O(n)\)；在最壞情況下，匹配成功的趟數為 \(n-m+1\)，每趟比較次數為 \(m\)，總比較次數為 \(m(n-m+1)\)，故時間複雜度為 \(O(mn)\)。

BF 算法匹配失敗時，在最好情況下，每趟不成功的匹配都發生在模式串的第一個字符，BF 算法要執行 \(n-m+1\) 次比較，時間複雜度為 \(O(n)\)；在最壞情況下，每趟不成功的匹配都發生在模式串的最後一個字符，BF 算法要執行 \(m(n-m+1)\) 次比較，時間複雜度為 \(O(mn)\)。

如果模式串有至少兩個不同的字符，則 BF 算法的平均時間複雜度為 \(O(n)\)。但是在 OI 題目中，給出的字符串一般都不是純隨機的。

Hash 的方法

參見：字符串哈希

KMP 算法

參見：前綴函數與 KMP 算法

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用