1. 數據結構-串的模式匹配
串的模式匹配就是子串定位操作。給定兩個串s="s0 s1 ... s(n-1)"和t="t0 t1 ... t(m-1)"（其中n和m分別是串s和t的長度），在主串s中尋找子串t的過程稱為模式匹配，t稱為模式。如果在s中找到等於t的子串，則稱匹配成功，返回t在s中的首次出現的下標位置；否則匹配失敗，返回-1。
本文介紹三個串模式匹配演算法，分別是簡單回溯演算法（Brute-Force，BF演算法）、KMP演算法、KMP演算法的改進。
從主串s的第0個字元開始，與模式串t的第0個字元開始逐字元比較，不相同時回溯到模式串t的第0個和主串s的第1個字元，重新開始比較。以此類推，直到t的所有字元完成匹配，則匹配成功，否則匹配失敗。
BF演算法速度慢的原因是存在大量不必要的回溯，即在某一趟與t的匹配過程失敗後，需要返回s串開始字元的下一字元重新開始比較，這對於某些模式串t來說是不必要的。例如，若s=12123123132，t=12313，在t與12 12312 3132中加粗子序列進行比較時，在 2 處發生失配，BF演算法接下來將t與121 23123 132、1212 31231 32、12123 12313 2比較。由於t中的231、312與其開始的123並不相同，顯然t與121 23123 132、1212 31231 32的比較是不必要的。
KMP演算法就是利用模式串中與模式串開頭部分子串的重復性來減少重復回溯，實現新一輪比較的直接跳轉。 具體來說，KMP演算法利用一個數組記錄模式串中每一個字元前面有幾個字元與模式串從頭重復，在與s串比較失配時，直接跳轉到重復子串的下一個字元繼續比較，而不用跳轉至模式串t的第0個字元。
演算法步驟： ①計算跳轉數組next。②利用KMP演算法進行模式匹配。
next數組通過遞推計算，即如果當前字元 t[j] 的前一個字元 t[j-1] 與其 next[j-1] 指向的字元 t[next[j-1]] 相同，意味著 t[j] 前的 next[j-1]+1 個字元與從 t[0] 到 t[next[j-1]] 的子串相同，因此 next[j]=next[j-1]+1 ；如果不相同，則遞推至 t[next[j-1]] 的next值指向的字元，與 t[j-1] 比較，直到確認 t[j] 前與 t 串從頭重復的字元數，或者無重復字元標記為 0 。
注意此處的函數返回參數類型為int*，用於 返回一位數組 ，且返回的這個一位數組必須在函數中用static定義。
KMP演算法進行模式匹配時，只需在回溯時將 j 指針賦值為 next[j] 。需要注意的是，若 next[j] 為 -1 ，則意味著 t[j] 前面沒有與 t 從頭重復的字元，且 t[j] 與 s[i] 失配，則 i 和 j 均加 1 。
考慮更特殊的模式串，還能進一步減少不必要的回溯次數。例如，s=111211112，t=11112，按照上述next的計算方式，next={-1,0,1,2,3}。當 i=3, j=3 時失配，此時 s[i]=2, t[j]=1 ，由於 next[j]=2 ，於是 j 跳轉為 2 ，t=11 1 12與s=111 2 11112比較。由於 t[next[j]]=t[j] 也為 1 ，必然與 s[i]=2 不相同，顯然這次回溯也不必要。
總結來說， 當失配的字元與待跳轉的字元相同時，跳轉一步並無意義，可再跳一步 ，即將當前字元置為跳轉後字元的next值。
2. 數據結構模式匹配求next值，主串abcaabccacabcabcaaaabc，模式abcabcaaa，怎麼求next值，詳細通俗點的過程
例如：
1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next值 0 1 1 2 2 3 1 2
next數組的求解方法是：第一位的next值為0，第二位的next值為1，後面求解每一位的next值時，根據前一位進行比較。首先將前一位與其next值對應的內容進行比較，如果相等，則該位的next值就是前一位的next值加上1；如果不等，向前繼續尋找next值對應的內容來與前一位進行比較，直到找到某個位上內容的next值對應的內容與前一位相等為止，則這個位對應的值加上1即為需求的next值；如果找到第一位都沒有找到與前一位相等的內容，那麼需求的位上的next值即為1。
方法有幾種, 我現在只明白了這一種. 還有一種是 前面第一個next值為 -1開始的.
3. 模式匹配 pattern-matching (數據比較)
要理解模式匹配(pattern-matching)，先把這兩個單詞拆開，先理解什麼是 模式(pattern) ，這里所的模式並不是設計模式里的模式，而是數據結構上的，這個模式用於描述一個結構的組成。
我們很容易聯想到「 正則表達」里的模式 ，不錯，這個pattern和正則里的pattern相似，不過適用范圍更廣，可以針對 各種類型的數據結構 ，不像正則表達只是針對字元串。比如正則表達式里"^A.*"這個pattern 表示以A開頭、後續一個或多個字元組成的字元串； List("A", _, _*)也是個pattern，表示第一個元素是」A」，後續一個或多個元素的List。
狹義的看，模式可以當作對某個類型，其內部數據在結構上抽象出來的表達式。如上面的List("A", _, _*)就是一種List結構的pattern。模式匹配(pattern-matching)則是匹配變數是否符合這種pattern。比如List("A","B")和List("A","X","Y")就符合上面的pattern，而List("X")則不符合。
例子中的：Array(1,2,3)，List("A",_,"C")等都是模式，表示由指定元素組成的某種類型。
當然模式也不僅僅是表示某種結構的，還可以是常量，或類型，如：
在 scala里對pattern有明確的定義，在形式上有以下幾種pattern：
1） 常量模式(constant patterns) 包含常量變數和常量字面量
常量模式和普通的 if 比較兩個對象是否相等(equals) 沒有區別，並沒有感覺到什麼威力
2) 變數模式(variable patterns)
確切的說單純的變數模式沒有匹配判斷的過程，只是把傳入的對象給起了一個新的變數名。
scala> site match { case whateverName => println(whateverName) }
上面把要匹配的 site對象用 whateverName 變數名代替，所以它總會匹配成功。不過這里有個約定，對於變數，要求必須是以小寫字母開頭，否則會把它對待成一個常量變數，比如上面的whateverName 如果寫成 WhateverName 就會去找這個 WhateverName 的變數，如果找到則比較相等性，找不到則出錯。
變數模式通常不會單獨使用，而是在多種模式組合時使用，比如
List(1,2) match{ case List(x,2) => println(x) }
裡面的x就是對匹配到的第一個元素用變數x標記。
3) 通配符模式(wildcard patterns)
通配符用下劃線表示："_"，可以理解成一個特殊的變數或佔位符。
單純的通配符模式通常在模式匹配的最後一行出現，case _ =>它可以匹配任何對象，用於處理所有其它匹配不成功的情況。
通配符模式也常和其他模式組合使用：
scala> List(1,2,3) match{ case List(_,_,3) => println("ok") }
上面的List(_,_,3)里用了2個通配符表示第一個和第二個元素，這2個元素可以是任意類型
通配符通常用於代表所不關心的部分，它不像變數模式可以後續的邏輯中使用這個變數。