字元串匹配演算法：Sunday演算法

背景

我們第一次接觸字元串匹配，想到的肯定是直接用2個循環來遍歷，這樣程式碼雖然簡單，但時間複雜度卻是\(Ω(m*n)\)，也就是達到了字元串匹配效率的下限。於是後來人經過研究，構造出了著名的KMP演算法（Knuth-Morris-Pratt演算法），讓我們的時間複雜度降低到了\(O(m+n)\)，但現代文字處理器中，卻很少使用KMP演算法來做字元串匹配，因為還是太慢了。現在主流的演算法是BM演算法（Boyer-Moore演算法），成功讓平均時間複雜度降低到了\(O(m/n)\)，而Sunday演算法，則是對BM演算法的進一步小幅優化。

KMP演算法很多人看了一遍遍以後，對next[n]數組的理解還是有點困難（包括筆者），寫程式碼的時候總是容易變成這種情況（/捂臉.jpg）：

（切到網頁）：馬冬梅

（切到編譯器）：馬什麼梅

（切到網頁）：馬冬梅

（切到編譯器）：馬冬什麼

（切到網頁）：馬冬梅

（切到編譯器）：什麼冬梅

而Sunday演算法，理解起來則是非常容易，同時極低的時間複雜度，讓Sunday演算法成為了我目前最常使用的字元串匹配演算法

Sunday 演算法是 Daniel M.Sunday 於 1990 年提出的字元串模式匹配。其效率在匹配隨機的字元串時比其他匹配演算法還要更快。Sunday 演算法的實現可比 KMP，BM 的實現容易太多。

平均性能的時間複雜度為\(O(n)\)；
最差情況的時間複雜度為\(O(n * m)\)。

演算法過程

Sunday演算法和BM演算法稍有不同的是，Sunday演算法是從前往後匹配，在匹配失敗時關注的是主串中參加匹配的最末位字元的下一位字元。

如果該字元沒有在模式串中出現則直接跳過，即移動位數 = 模式串長度 + 1；
否則，其移動位數 = 模式串長度 - 該字元最右出現的位置(以0開始) = 模式串中該字元最右出現的位置到尾部的距離 + 1。

現在舉個例子講解Sunday演算法

假定主串為 "HERE IS A SIMPLE EXAMPLE"，模式串為 "EXAMPLE"。

（1）

從頭部開始比較，發現不匹配。則 Sunday 演算法要求如下：找到主串中位於模式串後面的第一個字元，即紅色箭頭所指的 "空格"，再在模式串中從後往前找 "空格"，沒有找到，則直接把模式串移到 "空格" 的後面。

（2）

依舊從頭部開始比較，發現不匹配。找到主串中位於模式串後面的第一個字元 L，模式串中存在 L，則移動模式串使兩個 L 對齊。

（3）

找到匹配。

完整程式碼

#include <iostream>
#include <string>

#define MAX_CHAR 256
#define MAX_LENGTH 1000

using namespace std;

void GetNext(string & p, int & m, int next[])
{
	for (int i = 0; i < MAX_CHAR; i++)
		next[i] = -1;
	for (int i = 0; i < m; i++)
		next[p[i]] = i;
}

void Sunday(string & s, int & n, string & p, int & m)
{
	int next[MAX_CHAR];
	GetNext(p, m, next);

	int j;  // s 的下標
	int k;  // p 的下標
	int i = 0;
	bool is_find = false;
	while (i <= n - m)
	{
		j = i;
		k = 0;
		while (j < n && k < m && s[j] == p[k])
			j++, k++;

		if (k == m)
		{
			cout << "在主串下標 " << i << " 處找到匹配\n";
			is_find = true;
		}

		if (i + m < n)
			i += (m - next[s[i + m]]);
		else
			break;
	}

	if (!is_find)
		cout << "未找到匹配\n";
}

int main()
{
	string s, p;
	int n, m;

	while (cin >> s >> p)
	{
		n = s.size();
		m = p.size();
		Sunday(s, n, p, m);
		cout << endl;
	}

	return 0;
}

數據測試如下：

here#is#a#example
example
在主串下標 10 處找到匹配

aaa
a
在主串下標 0 處找到匹配
在主串下標 1 處找到匹配
在主串下標 2 處找到匹配

aaa
b
未找到匹配

附小吳師兄的動畫講解鏈接

Sunday演算法的缺點

看上去簡單高效非常美好的Sunday演算法，也有一些缺點。因為Sunday演算法的核心依賴於move數組，而move數組的值則取決於模式串，那麼就可能存在模式串構造出很差的move數組。例如下面一個例子

主串：baaaabaaaabaaaabaaaa

模式串：aaaaa

這個模式串使得move[a]的值為1，即每次匹配失敗時，只讓模式串向後移動一位再進行匹配。這樣就讓Sunday演算法的時間複雜度飆升到了O(m*n)，也就是字元串匹配的最壞情況,在這種情況下效率就明顯低於KMP等演算法了例如：HDU1686

總結

當然，也不能因為存在最壞的情況就直接否定Sunday演算法，大多數情況下，Sunday依然是一個簡單高效的演算法，值得我們熟練學習掌握。

Tags: 演算法基礎：字元串匹配