String Matching(字串比對)
寫作業的時候，常常需要從某個文章中找出「特定的單詞」，在這邊和大家介紹字串比對演算法的概念～～
這是從某文章部份擷取下來：
The advisory comes after the EU decided to add Taiwan to a list of nations approved for non-essential travel within the union and Schengen area, according to a MOFA press release. Countries on the list must meet certain criteria including logging less than 75 COVID-19 cases per 100,000 over 14 days and having a sample rate of less than 4 percent within seven days.
其中我想要找 Schengen這個詞，就需要靠字串比對的技術，來完成。
此字串比對和之前在 Dynamic Programming中，所提到的 LCS不太一樣。
Outline:
- Naive String-Matching Algorithm
- The Rabin-Karp Algorithm
- String Matching with Finite Automata
Naive String-Matching Algorithm
最直覺的字串比對方法，一個字一個字逐一去做比對。
其中s代表，shift，也就目前移動幾格。
Text：被比對的文章，長度：m（在推時間複雜度時會用到）
Pattern：目標字串，長度：n
Naive String Matching Algorithm特色:
- 暴力法
- 比對時使用：hashing function
- 時間複雜度：O(mn)
O(mn)=m(n-m+1)=mn-m²+m=O(mn)(m≤n)
使用範例：
The Rabin-Karp Algorithm
剛剛所說的演算法，一個一個逐一做比對，而Rabin-Karp則是一次選取一個範圍(window)，把「看起來相像(Looks Like)」的記錄下來，最後再從「看起來相像」中，和真正要找的字串做比對，將不一樣的剔除。
這邊可能不會講得非常詳細，範圍怎麼移動之類的，主要是想主要是想介紹其中的概念。
什麼叫「看起來相像(Looks Like)」？
在電腦中，它只看得懂數字化的東西，所以把Abc…丟進去，電腦一定看不懂。所以我們會把abc…轉成數字類型。
有了基本的概念後，再來看這個。
先以數字來做舉例，比較容易了解。
字串 ”31415”，我們會轉成「十進位的」數字型態的 31415。然後用一個小技巧 — Modulo，算出他們的餘數(R)後，先放在一旁。
再從原本要找的一堆數字中，圈選裡面數字，同樣的也去做一次 Modulo，最後再比對依序和 R比對，如果算出來的結果是一樣的話，我們會說他們「看起來可能一樣」，因為有些也可能只是湊巧相同，所以最後還要再和原本的 Pattern做一次真正的比對，確定我們的最終答案。
上下兩圖比較後，有沒有感受到視窗(window)移動的概念是什麼了呢？
完整範例：
前面說到「看起來相像(Looks Like)」的意思是，
他們 mod(取餘數 )後相同
以上面為例，找到兩個數字Mod後，皆為7。然後再用這兩個字串，和原本的字串(Pattern)做真正的比對，找到哪些才是真正相同的字串。
mod的階段，可以想像成是「篩選」的一個步驟，把有可能的字串留下，再做比較。
String Matching with Finite Automata
整個運作流程的說明：
主要特色：
- 建立一個有限狀態機(Finite Automata)來辨識字串
- 空間複雜度：需要於外的空間O(m|∑|)來存放table
- 尋找階段時間複雜度：Θ(n)
狀態表、狀態圖都建好後，要怎麼去文章中尋找字串？
假設今天我想要從 T = abababacaba中，找到是否有 ababaca這個字串時，只要將 T字串放到 Digram中，依照規則讓他跳來跳去，紀錄過程中出現幾次Accept的狀態，就可以知道，整個文章跟 Pattern Match到幾次。
什麼是有限狀態機(Finite Automata)
要構成一個有限狀態機，需要四個條件：
以上都只是數學上面給他做的定義，如果只是用紙筆來算的話，其實不用需要考慮到這麼多，但這邊還是小提一下。
我們主要是利用「有限狀態機」的特性，去把狀態表、狀態圖給建立出來。其中比較需要注意的是，狀態表跟狀態圖要怎麼畫。（有了表格，圖自然而然也好畫）
狀態表的畫法
先想如果要成功Accept，總共會需要幾個state(其實即是Pattern的長度+1)，其中state跟state之間會如何運作，也要一併列出。
綠色圓圈代表，我現在已經成功配對一個a，位於state1，等待下一個輸入，如果input=b，則會進入state2。
其他以此類推。
其他空格要怎麼填呢？
記得state代表，目前已經配對好幾個Pattern中的字元！！
為什麼這邊填 0?
如果已經走到那格，代表目前輸入為a b a b b，用此輸入和Pattern做比對，發現兩個沒有任何共通字元。
回到初始狀態state 0
注意：比對過程中，Input逐漸往後面做比較，而Pattern則是往前做比較。
Input往後面移動的原因：如果Input的前半段沒有對應到Pattern，理當後面也不會對應到Pattern上。所以往後的原因，是想要知道，那Input的後面是否有可能會對應到某部分的Pattern。
Pattern往前面慢慢移動的原因：如果後面沒有比對到的話，理當前面也不可能有對應到，所以往前面慢慢去做比對。
為什麼這邊填 4?
如果已經走到那格，代表目前輸入為a b a b a b，用此輸入和Pattern做比對，發現有4個相同字元
回到狀態state 4
其他以此類推。
如果可以畫出狀態表的話，相信狀態圖對各位來說也不是什麼件難事，這邊就不多做細說。
主要是從老師上課內容，再自行做成筆記，如有錯誤還請各位多多指教～～
這篇也是花了好久才產出，希望能幫助需要的夥伴。
那我們下次再見囉～～
