Rob Pike, 最偉大的C 語言大師之一, 在《Notes on C Programming》中闡述了一個(gè)原則：花哨的算法比簡(jiǎn)單算法更容易出bug、更難實(shí)現(xiàn)，盡量使用簡(jiǎn)單的算法配合簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。而Ken Thompson——Unix 最初版本的設(shè)計(jì)者和實(shí)現(xiàn)者，禪宗偈語般地對(duì)Pike 的這一原則作了強(qiáng)調(diào)： 拿不準(zhǔn)就窮舉（When in doubt , use brute force）。 而對(duì)于裝13愛好者來說，更是自豪的稱其使用的是BF算法。
窮舉法用在字符串匹配上，簡(jiǎn)單的描述就是，檢查文本從0到n-m的每一個(gè)位置，看看從這個(gè)位置開始是否與模式匹配。這種方法還是有一些優(yōu)點(diǎn)的，如：不需要預(yù)處理過程，需要的額外空間為常數(shù)，每一趟比較時(shí)可以以任意順序進(jìn)行。
盡管它的時(shí)間復(fù)雜度為O(mn)，例如在文本"aaaaaaaaaaaaaaaaaaaaaaaaaaa"中尋找"aaaaab"時(shí)，就完全體現(xiàn)出來了。但是算法的期望值卻是2n，這表明該算法在實(shí)際應(yīng)用中效率不低。
C代碼如下：
- void BF(char *x, int m, char *y, int n) {
- int i, j;
-
-
- for (j = 0; j <= n - m; ++j) {
- for (i = 0; i < m && x[i] == y[i + j]; ++i);
- if (i >= m)
- OUTPUT(j);
- }
- }
-
如果我們注意到C庫函數(shù)是匯編優(yōu)化過的，并通常能提供比C代碼更高的性能的話，我們可以用memcmp來完成每一趟比較過程，從而達(dá)到更好的性能：
- #define EOS '\0'
-
- void BF(char *x, int m, char *y, int n) {
- char *yb;
-
- for (yb = y; *y != EOS; ++y)
- if (memcmp(x, y, m) == 0)
- OUTPUT(y - yb);
- }
-
自動(dòng)機(jī)的方法其實(shí)和窮舉法有點(diǎn)相似，都是用最簡(jiǎn)單直白的方式來做事情。區(qū)別在于窮舉法是在計(jì)算，而自動(dòng)機(jī)則是查表。盡管自動(dòng)機(jī)的構(gòu)造過程有一點(diǎn)點(diǎn)難解，要涉及到DFA的理論，但是自動(dòng)機(jī)的比較過程那絕對(duì)是簡(jiǎn)單到無語。
簡(jiǎn)單說來，根據(jù)模式串，畫好了一張大的表格，表格m+1行σ列，這里σ表示字母表的大小。表格每一行表示一種狀態(tài)，狀態(tài)數(shù)比模式長度多1。一開始的狀態(tài)是0，也就是處在表格的第0行，這一行的每個(gè)元素指示了當(dāng)遇到某字符時(shí)就跳轉(zhuǎn)到另一個(gè)狀態(tài)。每當(dāng)跳轉(zhuǎn)到最終狀態(tài)時(shí)，表示找到了一個(gè)匹配。
語言表述起來還是比較啰嗦，看代碼就知道了：
- #define ASIZE 256
-
- int preAut(const char *x, int m, int* aut) {
- int i, state, target, old;
-
- for (state = 0, i = 0; i < m; ++i) {
- target = i + 1;
- old = aut[state * ASIZE + x[i]];
- aut[state * ASIZE + x[i]] = target;
- memcpy(aut + target * ASIZE, aut + old * ASIZE, ASIZE*sizeof(int));
- state = target;
- }
- return state;
- }
-
-
- void AUT(const char *x, int m, const char *y, int n) {
- int j, state;
-
-
- int *aut = (int*)calloc((m+1)*ASIZE, sizeof(int));
- int Terminal = preAut(x, m, aut);
-
-
- for (state = 0, j = 0; j < n; ++j) {
- state = aut[state*ASIZE+y[j]];
- if (state == Terminal)
- OUTPUT(j - m + 1);
- }
- }
（注：原文的代碼使用一個(gè)有向圖的數(shù)據(jù)結(jié)構(gòu)，我遵循大師的指引，改用了更簡(jiǎn)單一點(diǎn)的數(shù)組）
從代碼上我們很容易看出，自動(dòng)機(jī)的構(gòu)造需要時(shí)間是O(mσ)，空間也是O(mσ)（嚴(yán)格來說這份代碼使用了O((m+1)σ)），但是一旦構(gòu)造完畢，接下來匹配的時(shí)間則是O(n)。
匹配的過程前面已經(jīng)說了，太簡(jiǎn)單了沒什么好說的，這里就解釋一下構(gòu)造過程吧！
我們構(gòu)造的目標(biāo)是對(duì)應(yīng)模式長度，構(gòu)造出同樣多的狀態(tài)，用0表示初始狀態(tài)，然后第一個(gè)字符用狀態(tài)1表示，第二個(gè)用狀態(tài)2表示，依次類推，直到最后一個(gè)字符，用m表示，也是最終狀態(tài)。
一開始，數(shù)組全都置0，，這個(gè)時(shí)候的自動(dòng)機(jī)遇到任何字符都轉(zhuǎn)到初始狀態(tài)。然后給它看模式的第一個(gè)字符，假設(shè)這是'a'吧，告訴它，狀態(tài)0遇到'a'應(yīng)該到一個(gè)新的狀態(tài)——狀態(tài)1，所以把第0行的第'a'列修改為1。而這個(gè)時(shí)候狀態(tài)1還是空白的，怎么辦呢？
這時(shí)候狀態(tài)0就想呀，在我被告知遇到'a'要去狀態(tài)1之前，我原本遇到'a'都要去狀態(tài)0的，也就是修改之前第'a'列所指的那個(gè)狀態(tài)，稱為old狀態(tài)吧；而現(xiàn)在我遇到'a'卻要去一個(gè)新的狀態(tài)，既然以前old狀態(tài)能處理遇到'a'之后的事情，那么我讓新的狀態(tài)像old狀態(tài)一樣就好了。于是狀態(tài)0把old狀態(tài)拷貝到狀態(tài)1。
現(xiàn)在輪到狀態(tài)1了，給它看第二個(gè)字符，它也如法炮制，指向了狀態(tài)2，又把old狀態(tài)拷貝給了狀態(tài)2。
于是，狀態(tài)機(jī)就在這種代代傳承的過程中構(gòu)造完畢了。
雖然理論上自動(dòng)機(jī)是最完美的匹配方式，但是由于預(yù)處理的消耗過大，實(shí)踐中，主要還是用于正則表達(dá)式。
結(jié)語：窮舉法與自動(dòng)機(jī)各自走了兩個(gè)極端，因此都沒能達(dá)到綜合性能的最佳，本文之后介紹的算法，可以看成是在窮舉和自動(dòng)機(jī)兩者之間取舍權(quán)衡的結(jié)果。