LeetCode 466. 統計重複個數
題目
由 n 個連接配接的字元串 s 組成字元串 S，記作 S = [s,n]。例如，["abc",3]=“abcabcabc”。
如果我們可以從 s2 中删除某些字元使其變為 s1，則稱字元串 s1 可以從字元串 s2 獲得。例如，根據定義，"abc" 可以從 “abdbec” 獲得，但不能從 “acbbe” 獲得。
現在給你兩個非空字元串 s1 和 s2(每個最多 100 個字元長)和兩個整數 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。現在考慮字元串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。
請你找出一個可以滿足使[S2,M] 從 S1 獲得的最大整數 M 。
示例：
輸入：
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2
傳回：
2
來源：力扣(LeetCode)
連結：https://leetcode-cn.com/problems/count-the-repetitions
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
解題思路
一句話：求n1個s1拼接形成的S1删除若幹字元後可以分成多少個由n2個s1拼接形成的S2；
思路1-尋找“循環節”然後根據循環節倍數關系求解
“循環節”是指若幹個s1拼接起來删除若幹字元後能得到一個S2，看圖解：
是以，思路是先找“循環節”，然後看n1個s1拼接的S1中有多少個這樣的循環節片段，再處理循環節前後剩餘的一丢丢殘餘的s1片段，就能從S1中得到N個完整的s1，N/n2就得到了題目要求解的M值；
步驟：
從n1個s1中順序比對s2中的字元，記錄完整比對s2的數量，每比對完一個s1就記錄目前比對到的s2的數量并記錄比對完第一個s1時s2中的待比對字元索引位置；
在後續中若某次比對完s1後在s2中的停止處索引等于首次的說明找了“循環節”，就可以按照上面說的思路開始數學計算；
若始終未找到循環節，則隻能暴力比對完n1個s1，有兩種情況：
s2中的字元有的在s1中不存在，0比對(可做特例先行判斷，避免後面的無意義計算)；
n1個s1處理後的長度恰隻夠一個S2，1比對；
算法複雜度:
len1為s1長度，len2為s2長度，n1即題中n1個s1的n1
時間複雜度： $ {color{Magenta}{Omicronleft(len1 ast len2right)}} $ 最壞時為n1(ast)len1(ast)len2
空間複雜度： $ {color{Magenta}{Omicronleft(n1right)}} $ 需要n1長度數組存s2的比對數
算法源碼示例
package leetcode;
public class LeetCode_0466 {
}
class Solution_0466 {
public int getMaxRepetitions_1(String s1, int n1, String s2, int n2) {
int len1 = s1.length();
int len2 = s2.length();
// 特例判斷
if (n1 == 0 || n2 == 0 || n1 * len1 < n2 * len2) {
return 0;
}
// 特例-若s2中字元有不在s1中的直接傳回
char[] cs2 = s2.toCharArray();
for (char c : cs2) {
if (s1.indexOf(c) == -1) {
return 0;
}
}
char[] cs1 = s1.toCharArray();
// 尋找循環體時s2的下标
int index = 0;
int count = 0;
// 在s2中首次比對到的字元索引位置
int firstIndex = 0;
// 記錄在s1的第i次拼接時比對到的s2的總數
int[] countRdecoder = new int[n1];
for (int i = 0; i < n1; i++) {
for (int j = 0; j < len1; j++) {
// 這是一個往複比對，比對到s1中的s2時就右移index，完全比對s2時記錄count并重置index
if (cs2[index] == cs1[j]) {
index++;
if (index == len2) {
count++;
index = 0;
}
}
}
// 首次比對完時s1的停止位置
if (i == 0) {
firstIndex = index;
}
// 截至本次總比對s2的數量
countRdecoder[i] = count;
// 若本次的停止位index與第一次時的停止位相同說明找到了循環體，開始數學計算并傳回
if (i != 0 && index == firstIndex) {
// 第一部分：找到循環體時循環體内的比對s1數量乘以n1個s2中有多少個這樣的循環體片段(n1 - 1) / i)
int part1 = ((n1 - 1) / i) * (countRdecoder[i] - countRdecoder[0]);
// 第二部分：除去第一部分後剩餘部分s2拼接起來可比對s1的數量
int part2 = countRdecoder[(n1 - 1) % i];
// 總比對s1的數量除以n2(n2個s1)即得題目要求的M
return (part1 + part2) / n2;
}
}
// 若未找到循環體 ，則直接暴力求解，這種情況基本隻能是0或1了
return countRdecoder[n1 - 1] / n2;
}
}