459.重複的子字元串--LeetCode

題目描述

給定一個非空的字元串，判斷它是否可以由它的一個子串重複多次構成。給定的字元串隻含有小寫英文字母，并且長度不超過10000。

算法

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s in (s+s)[1:-1]
           

這是一道簡單題。但是可以探讨的内容有很多。

1. 如何判斷符合條件？

   最簡單的方法就是使用必要條件：即如果一個字元串由一個子串重複多次構成，以最簡單的2次重複子串

   aabaab

   為例,那麼将該字元串連續重複一次，必然會在第二個字元與倒數第二個字元之間找到該字元串，即尾子串+首子串=首子串+尾子串。

2. 那麼問題就變成了如何在一個字元串中尋找模式串。

   我們可以使用python自帶的in方法或者substr方法；同樣，我們也可以使用著名的KMP算法

3. KMP算法

void Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
         j++;k++;
         next[j] = k;
      }
      /*此處為KMP尋找next清單的點睛之筆，事實上原理與使用KMP尋找子串的方法相同
      * j和k先後進入模式串，尋找結尾與開頭相同的k。從模式串頭部開始，如果j與k所指的字元相同則j和k繼續前進，并記錄下next[j]，如果出現
      * 不相同的情況，k指針需要回退到與t[k-1]之前都相同的上一個位置，采用最近跳，以防止錯過可能的比對串。
      *
      */
      else k = next[k];//重點難點！
   }
}

int KMP(String s,String t)
{
   int next[MaxSize],i=0;j=0;
   Getnext(t,next);
   while(i<s.length&&j<t.length)
   {
      if(j==-1 || s[i]==t[j])
      {
         i++;
         j++;
      }
      else j=next[j];               //j回退。。。
   }
   if(j>=t.length)
       return (i-t.length);         //模式串完全比對成功才算找到可以停止，傳回子串的位置
   else
      return (-1);                  //沒找到
}
           

代碼中與圖中next依次減一。