<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Simple Match - 簡單匹配 -------- #### 問題 在文本$$ text $$中查找字符串$$ pattern $$出現的所有位置（$$ text $$長度為$$ n $$，$$ pattern $$長度為$$ m $$，$$ n, m $$都是正整數且$$ n \gt m $$）。 #### 解法 對于$$ text[0 \dots n] $$，從$$ i = 0, j = 0 $$開始，依次比較$$ text[i+j] = pattern[j] $$。若相等則$$ j $$向后移動一個位置再繼續比較，直到$$ j \ge m $$，即$$ text[i \dots i+m-1] = pattern[0 \dots m-1] $$，說明$$ pattern $$在$$ text $$的$$ i $$下標出現；否則$$ i = i+1, j = 0 $$重新開始新一輪匹配。 下面演示一個匹配的過程：  $$ (1) $$ 從$$ text $$第$$ 0 $$個字符開始匹配，有$$ text[0 \dots 2] = pattern[0 \dots 2]，text[3] \ne pattern[3] $$，繼續匹配下一個字符；  $$ (2) $$ 從$$ text $$第$$ 1 $$個字符開始匹配，有$$ text[1] \ne pattern[0] $$，繼續匹配下一個字符； $$ \cdots $$  $$ (3) $$ 從$$ text $$第$$ 7 $$個字符開始匹配，$$ text[7 \dots 10] = pattern[0 \dots 3] $$，匹配成功，算法結束； 顯然，對于$$ text $$中的每個位置$$ i $$，都需要進行一次匹配，而每次匹配的平均時間復雜度為$$ pattern $$的長度$$ m $$。該算法的時間復雜度為$$ O(m \times n) $$。 -------- #### 源碼 [SimpleMatch.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/SimpleMatch.h) [SimpleMatch.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/SimpleMatch.cpp) #### 測試 [SimpleMatchTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/SimpleMatchTest.cpp)