九章演算法 | Google 面試題 : 重複子字元串模式

撰文 | JZ

專欄 | 九章演算法

題目描述

對於一個非空字元串，判斷其是否可由一個子字元串重複多次組成。

字元串只包含小寫字母且長度不超過10000。

樣例 1

輸入 "abab"n輸出 Truen

樣例解釋

樣例 2

輸入 "aba"n輸出 Falsen

樣例 3

輸入 "abcabcabcabc"n輸出 Truen

樣例解釋

輸入可由"abc"重複四次組成

解題思路

1

一個簡單的思路是，枚舉子字元串的長度lenSub<len(len為原字元串長度)，將原字元串分成多個子字元串，每個子字元串長度為lenSub（由此可見，lenSub整除len），再判斷這些子字元串是否全部相等，若全部相等，則返回True，如果對於所有lenSub均不滿足該條件，則返回False。時間複雜度為O(len*v(len))，其中v(len)為len的因數個數（因為我們只需要對整除len的lenSub進行進一步判斷）。

2

下面再說一種神奇的方法，由kmp演算法中的next數組實現。

1.字元串s的下標從0到n-1，n為字元串長度，記s(i)表示s的第i位字元，s(i,j)表示從s的第i位到第j位的子字元串，若i>j，則s(i,j)=」」(空串）。

2.next數組的定義為：next(i)=p，表示p為小於i且滿足s(0 , p) = s(i-p , i)的最大的p，如果不存在這樣的p，則next(i) = -1，顯然next(0) = -1。我們可以用O(n)的時間計算出next數組。假設我們已知next(0)，next(1)，……，next(i-1) ，現在要求next(i)，不妨設next(i-1) = j0，則由next數組定義可知s(0 , j0) = s(i-1-j0 , i-1)。

若s(j0+1) = s(i)，則結合s(0 , j0) = s(i-1-j0 , i-1)可知s(0 , j0+1) = s(i - (j0+1) , i)，由此可知，next(i)=j0+1。

若s(j0+1)!=s(i)但s(next(j0)+1)=s(i)，記j1=next(j0)，則s(j1+1)=s(i)，由next數組的定義，s(0 , j1) = s(j0 - j1 , j0) = s(i - 1 - j1 , i - 1)，即s(0，j1) = s(i - 1 - j1 , i - 1)，由假設s(j1+1) = s(i)，則s(0 , j1+1) = s(i - (j1+1) , i)，故next(i) = j1+1。

同前兩步的分析，如果我們能找到一個k，使得對於所有小於k的k0，s(j(k0)+1)!=s(i)，但有s(j(k)+1) = s(i)，則由next數組的定義可以得到next(i)=j(k)+1，否則需進一步考慮j(k+1) = next(j(k))，如果我們找不到這樣的k，則next(i)=-1。

3.對於字元串s，如果j滿足，0<=j<=n-1，且s(0，j) = s(n-1-j，n-1)，令k=n-1-j，若k整除n，不妨設n=mk，則s(0，(m-1)k - 1) = s(k，mk - 1)，即s(0，k-1) = s(k，2k-1) = …… = s((m-1)k - 1，mk - 1)，即s滿足題設條件。故要判斷s是否為重複子串組成，只需找到滿足上述條件的j，且k整除n，即說明s滿足條件，否則不滿足。

4.利用已算出的next(n-1)，令k=n-1-next(n-1)，由c可知，若k整除n，且k<n，則s滿足條件，否則不滿足。上述演算法的複雜度可證明為O(n)。

參考代碼

參考代碼給出了利用next數組求解的代碼。

面試官角度分析

這道題的第一種解法比較簡單，考察窮舉和字元串處理的能力，給出第一種方法並正確分析時間複雜度基本可以達到hire；如果面試者對KMP演算法有了解，可以給出第二種next數組的演算法可以達到strong hire。

九章答案鏈接

Repeated substring pattern 題解

LintCode 相關題目

Strstr 字元串查找