版本 f072e684b8c90503d5329bf4acc6472e6806d61d

String_Matching

Changes from f072e684b8c90503d5329bf4acc6472e6806d61d to de8f3dcfa862fb8abc294130b7beb8ea10945346

KMP
==========
Knuth-Morris-Pratt algorithm
---------------------------------------
使用時機：
給定A,B兩字串，尋找B字串是否存在A當中

當B的字串內容，本身有<b>重複的字串</b>時，可用KMP以減少重複否配的時間

ex:

B : aabaab

B字串本身重複 "aab"

![跳過重複字串](/acm/KMP_1.gif)


方法：先用fail function找出字串B重複的字串

Fail Function
------------------------
<b>目的：當否配失敗時，能知道字串B要對齊哪裡繼續否配</b>
 
![](/acm/KMP_2.gif)


變數：

B [ ] ... 存放字串B

pi [ ] ... 紀錄前一個重複字串出現的位置

cur_pos ... 目前字串重複的位置


初始化：

![  cur_pos 初始為 -1   pi[0] 初始為 -1](/acm/KMP_3.gif)

Z Algorithm
======================
Z_value
-----------------------------------
從第2個element開始以其為字首，去和以第1個element為首的字串比，找出最長相同字串的長度

![](/acm/zvalue.gif)