題目描述
這是 LeetCode 上的 1668. 最大重複子字元串 ，難度為 簡單。
Tag : 「動态規劃」、「序列 DP」、「字元串哈希」
給你一個字元串
sequence
，如果字元串
word
連續重複
k
次形成的字元串是
sequence
的一個子字元串，那麼單詞
word
的 重複值為
k
。
單詞
word
的 最大重複值 是單詞
word
在
sequence
中最大的重複值。如果
word
不是
sequence
的子串，那麼重複值
k
為
0
。
給你一個字元串
sequence
和
word
，請你傳回 最大重複值
k
。
示例 1：
輸入：sequence = "ababc", word = "ab"
輸出：2
解釋："abab" 是 "ababc" 的子字元串。 示例 2：
輸入：sequence = "ababc", word = "ba"
輸出：1
解釋："ba" 是 "ababc" 的子字元串，但 "baba" 不是 "ababc" 的子字元串。 示例 3：
輸入：sequence = "ababc", word = "ac"
輸出：0
解釋："ac" 不是 "ababc" 的子字元串。 提示：
-
sequence
word
序列 DP
為了友善，我們記
sequence
為
ss
，記
word
為
pp
，将兩者長度分别記為
n
和
m
。
同時我們調整「字元串」以及「将要用到的動規數組」的下标從
這是一道入門級的「序列 DP」運用題，容易想到 定義
為了考慮以
ss[i]
結尾時的最大重複值。
不失一般性考慮
該如何轉移：由于
pp
的長度已知，每次轉移
時我們可以從
ss
中截取 以
為結尾，長度為
sub
并與
pp
比對，若兩者相等，說明
sub
貢獻了大小為
的重複度，同時該重複度可累加在
上（好好回想我們的狀态定義），即有狀态轉移方程：
。
最終所有
Java 代碼：
class Solution {
public int maxRepeating(String ss, String pp) {
int n = ss.length(), m = pp.length(), ans = 0;
int[] f = new int[n + 10];
for (int i = 1; i <= n; i++) {
if (i - m < 0) continue;
if (ss.substring(i - m, i).equals(pp)) f[i] = f[i - m] + 1;
ans = Math.max(ans, f[i]);
}
return ans;
}
} TypeScript 代碼：
function maxRepeating(ss: string, pp: string): number {
let n = ss.length, m = pp.length, ans = 0
const f = new Array<number>(n + 10).fill(0)
for (let i = 1; i <= n; i++) {
if (i - m < 0) continue
if (ss.substr(i - m, i) == pp) f[i] = f[i - m] + 1
ans = Math.max(ans, f[i])
}
return ans
} Python 代碼：
class Solution:
def maxRepeating(self, ss: str, pp: str) -> int:
n, m, ans = len(ss), len(pp), 0
f = [0] * (n + 10)
for i in range(1, n + 1):
if i - m < 0:
continue
if ss[i - m:i] == pp:
f[i] = f[i - m] + 1
ans = max(ans, f[i])
return ans - 時間複雜度：
- 空間複雜度：
字元串哈希
解法一的轉移瓶頸在于：每次需要花費
該過程可用「字元串哈希」進行優化：将
ss
和
pp
進行拼接得到完整字元串，并計算完整字元串的哈希數組和次方數組。随後從前往後檢查
ss
，若「某個以
結尾長度為
m
的字尾字元串哈希值」與「
pp
字元串的哈希值」相等，說明找到了前驅狀态值
，可進行轉移。
我們通過
複雜度預處理了字元串哈希，将轉移過程中「複雜度為
的子串截取與字元串比較」替換成了「複雜度為
的數值對比」，整體複雜度從
下降到
。
不了解「字元串哈希」的同學可見前置 🧀 : 字元串哈希入門。裡面詳解字元串哈希基本原理以及哈希沖突簡單處理方式
Java 代碼：
class Solution {
public int maxRepeating(String ss, String pp) {
int n = ss.length(), m = pp.length(), ans = 0;
int[] f = new int[n + 10];
String s = ss + pp;
int P = 1313131, N = s.length();
long[] h = new long[N + 10], p = new long[N + 10];
p[0] = 1;
for (int i = 1; i <= N; i++) {
h[i] = h[i - 1] * P + s.charAt(i - 1);
p[i] = p[i - 1] * P;
}
long phash = h[N] - h[N - m] * p[m];
for (int i = 1; i <= n; i++) {
if (i - m < 0) continue;
long cur = h[i] - h[i - m] * p[m];
if (cur == phash) f[i] = f[i - m] + 1;
ans = Math.max(ans, f[i]);
}
return ans;
}
} Python 代碼：
class Solution:
def maxRepeating(self, ss: str, pp: str) -> int:
n, m, ans = len(ss), len(pp), 0
f = [0] * (n + 10)
s = ss + pp
P, N, MOD = 131, len(s), 987654321
h, p = [0] * (N + 10), [0] * (N + 10)
p[0] = 1
for i in range(1, N + 1):
h[i] = (h[i - 1] * P + ord(s[i - 1])) % MOD
p[i] = (p[i - 1] * P) % MOD
phash = (h[N] - h[N - m] * p[m]) % MOD
for i in range(1, n + 1):
if i - m < 0:
continue
cur = (h[i] - h[i - m] * p[m]) % MOD
if cur == phash:
f[i] = f[i - m] + 1
ans = max(ans, f[i])
return ans - 時間複雜度：
- 空間複雜度：
總結
這裡簡單說下「線性 DP」和「序列 DP」的差別。
線性 DP 通常強調「狀态轉移所依賴的前驅狀态」是由給定數組所提供的，即拓撲序是由原數組直接給出。更大白話來說就是通常有
依賴于
。
這就限定了線性 DP 的複雜度是簡單由「狀态數量（或者說是次元數）」所決定。
序列 DP 通常需要結合題意來尋找前驅狀态，即需要自身尋找拓撲序關系（例如本題，需要自己結合題意來找到可轉移的前驅狀态
）。
這就限定了序列 DP 的複雜度是由「狀态數 + 找前驅」的複雜度所共同決定。也直接導緻了序列 DP 有很多玩法，往往能夠結合其他知識點出題，來優化找前驅這一操作，通常是利用某些性質，或是利用資料結構進行優化。
最後
這是我們「刷穿 LeetCode」系列文章的第
No.1668
篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)