暴力字串比對

習題預習

1. 給出一個字符串和一個文本，找出其中所有相同的子字符串。例如，字符串「ab」在文本「abcabacbabdab」中出現了三次。

2. 找到一個字符串中重複出現的字母對。例如，在字符串「hello」中，「l」字母在第2個和第4個位置都出現了。

3. 給出兩個字符串A和B，找到A中所有出現在B中的子字符串。例如，在字符串「AABCA」和「ABCACB」中，共有兩個相同的子字符串「ABC」。

4. 給出一個文本和一個模式字符串，找到模式字符串在文本中的所有出現位置。例如，在字符串「abcabacbabdab」中查找模式字符串「ab」，將返回位置0、3、7和10。

5. 找到一個字符串中最長的回文子串（即從左到右和從右到左讀取相同的字符串）。例如，在字符串「babad」中，最長的回文子串是「bab」。

說明知識

Brute Force String Matching是一種字串搜尋演算法，可在一個較長的文字（T）中找到一個較短的字串（P）的開始位置。

演算法的基本思想是從T的第一個字符開始，依次與P的每一個字符進行比較，如果發現不匹配，則向右移動一個字符，再次從該位置開始進行比較，直到找到匹配的子串或者T中沒有剩餘的字符。

以下是Brute Force String Matching的例子：

假設T為"this is an example"，P為"ex"。可以從T的第一個字符"t"開始，依次與P的每一個字符進行比較。在T的第14個位置，也就是"e"字符的位置，發現該字符與P的第一個字符"e"相同，進行下一步比較。然後在T的第15個位置，也就是"x"字符的位置，發現該字符與P的第二個字符"x"相同，進行比較。由於最後一個字符匹配，所以找到了字串P，其開始位置為T中的第13個位置。

儘管Brute Force String Matching演算法簡單易懂，但是當字串長度較大時，它的效率會變得很低。這是因為需要逐個比較每一個字符，可能需要進行大量的比較操作。因此，在實際的應用中，需要選擇更有效率的字串搜尋演算法。

彙總重點

1. Brute Force String Matching是一種基本的模式匹配算法。

2. 該算法的核心思想是從給定字符串的第一個字符開始，逐個比較字符，直到找到匹配的字符序列。

3. 該算法需要遍歷所有可能的子串來進行匹配。

4. 該算法可以應用於任何字符串匹配問題，但是在大規模問題中，效率較低。

5. 實現Brute Force String Matching的關鍵是定義好匹配的成功條件和失敗條件。

6. 在實際應用中，可以使用其他高效的算法代替Brute Force String Matching來解決字符串匹配問題。

7. Brute Force String Matching的時間複雜度為O(mn)，其中n是主字符串的長度，m是模式字符串的長度。

8. Brute Force String Matching是一種簡單和易於理解的算法，適用於教學和基礎學習。

知識測驗

1. 問題描述：給出一個短字串P和一個長字串T，在T中查找所有匹配P的子串並輸出它們的開始位置。
   答案：https://www.geeksforgeeks.org/brute-force-algorithm-for-string-matching/

2. 問題描述：給出一個字典，將一個句子拆分成單詞，並返回所有可能的拆分方式。
   答案：https://leetcode.com/problems/word-break-ii/

3. 問題描述：給出一個文本和學生名單，查找每個學生在文本中出現的次數並返回一個包含每個學生名和他的出現次數的列表。
   答案：https://leetcode.com/problems/most-common-word/

4. 問題描述：給出一個模式和一個字元串，查找字元串中是否存在模式的非重疊出現。
   答案：https://leetcode.com/problems/repeated-substring-pattern/

5. 問題描述：給出一個長度為n的整數數組，找到其中所有相鄰數字同數的片段並返回數量。
   答案：https://leetcode.com/problems/arithmetic-slices/