---

這個方法是參考ＫＭＰ演算法的，如果已經會的可以直接跳過。

假如字串為：A B C A B B C

A B C A B B C

0

A B C A B B C

0 0

A B C A B B C

0 0 0 1              (發現重複)

A B C A B B C

0 0 0 1 2            (發現重複)

A B C A B B C

0 0 0 1 2 0

A B C A B B C

0 0 0 1 2 0 0

-----------------------------------------------------------------

以上的字串為最小字串，所以答案為1

-----------------------------------------------------------------

換一個簡單的範例： Ａ Ｂ Ｃ Ａ Ｂ Ｃ

Ａ Ｂ Ｃ Ａ Ｂ Ｃ

0

Ａ Ｂ Ｃ Ａ Ｂ Ｃ

0  0

Ａ Ｂ Ｃ Ａ Ｂ Ｃ

0  0  0 

Ａ Ｂ Ｃ Ａ Ｂ Ｃ

0  0  0  1                (發現重複)

Ａ Ｂ Ｃ Ａ Ｂ Ｃ

0  0  0  1  2            (發現重複)

Ａ Ｂ Ｃ Ａ Ｂ Ｃ

0  0   0  1  2  3       (發現重複)  

-----------------------------------------------------------------

以上範例最小字串為【ＡＢＣ】，所以答案為2

-----------------------------------------------------------------

觀察以上的兩個情況，可以使用【從右往左】數過來【第一個0的位置】來判斷，

1.【當0的位置】超過【字串長度一半】時，代表這個字串連一半都不能切割，所以答案必為1。

2.【當0的位置】不能整除【全部字串長度】時，代表不能剛好分割，所以答案為1。

3.【當0的位置】都符合時，答案就會是【全部字串長度】/【0的位置】。

4.【全部字串長度】如果一開始為１的話，不用檢查，答案為１。

以ＡＢＣＡＢＣ為例子，【全部長度】為6，最後一個【0的位置】為３      <---------  string的字元編號是從0開始，所以記得要把 （位置＋１）！！

答案為： ６/３ ＝ ２

以Ａ Ｂ Ａ Ｂ Ａ為例子，【全部長度】為５，最後一個【０的位置】為２

因為５％２ ！＝ ０，答案為：１

以A B C A B B C 為例子，發現Ｂ的位置沒有重複且超過【字串的一半】，所以答案為：１

-----------------------------------------------------------------

以上為自己思考的方法，如果有地方有問題，請各位提出來，感謝各位，希望能幫助到大家。

ＰＳ如果要加快速度，可能要在讀取的地方下手

AC（0.8s, 3.1MB）  >>>   AC（28ms, 2.3MB）

 

 

---

感謝解說，KMP演算法看懂了

 

另外我的程式無論如何都沒辦法把使用空間減到5MB以下，佩服