資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中的重複計數
假設我們有兩個非空字串 s1 和 s2（最多 100 個字元）和兩個數字 n1 和 n2，它們都在 0 到 106 的範圍內。現在假設字串 S1 和 S2，其中 S1=[s1,n1] 和 S2=[s2,n2]。
S = [s,n] 定義了一個字串 S，它由 n 個連線的字串 s 組成。例如，["ab", 4] ="abababab"。
另一方面，我們也可以定義，如果從字串 s2 中刪除一些字元後可以得到字串 s1，則可以說字串 s1 可以從字串 s2 中得到。“abc”可以從“abdbec”得到，但不能從“acbbe”得到。
我們需要找到最大的整數 M，使得 [S2,M] 可以從 S1 得到。
例如，如果輸入為 s1="acb", n1=4, s2="ab", n2=2，則輸出為 2
為了解決這個問題，我們將遵循以下步驟：
對於 s2 中的每個字元 c
如果 c 不在 s1 中，則：
返回 0
p1 := 0, p2 := 0, mark := 0
當 p1 < s1 的大小 時，執行：
c := s2[p2 mod s2 的大小]
當 (s1[p1 mod s1 的大小] 不等於 c 且 p1 < s1 的大小 * n1) 時，執行：
(將 p1 加 1)
(將 p2 加 1)
(將 p1 加 1)
如果 p2 mod s2 的大小 等於 0，則：
如果 p2 等於 s2 的大小，則：
mark := p1
否則，當 p1 mod s1 的大小 等於 mark mod s1 的大小 時，則：
round := (s1 的大小 * n1 - p1) / (p1 - mark)
p1 := p1 + round * (p1 - mark)
p2 := p2 + round * (p2 - s2 的大小)
返回 p2 / s2 的大小 / n2
示例
讓我們看看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
for (auto c : s2) {
if (s1.find(c) == string::npos)
return 0;
}
int p1 = 0, p2 = 0, mark = 0;
while (p1 < s1.length() * n1) {
char c = s2[p2 % s2.length()];
while (s1[p1 % s1.length()] != c && p1 <s1.length() * n1)
p1++;
p2++;
p1++;
if (p2 % s2.length() == 0) {
if (p2 == s2.length()) {
mark = p1;
}
else if (p1 % s1.length() == mark % s1.length()) {
int round = (s1.length() * n1 - p1) / (p1 - mark);
p1 += round * (p1 - mark);
p2 += round * (p2 - s2.length());
}
}
}
return p2 / s2.length() / n2;
}
};
main() {
Solution ob;
cout << (ob.getMaxRepetitions("acb",4,"ab",2));
}輸入
"acb",4,"ab",2
輸出
2
249 次瀏覽
