我必須找到給定字串的max(s.length * s.count)任何子s字串t，其中s.length是子字串的長度，s.count是s在t. 子串可以在 內重疊t。
示例：對于 string aaaaaa，子字串aaa具有最大值（出現次數 * 長度），子字串和出現次數為：
a: 6
aa: 5
aaa: 4
aaaa : 3
aaaaa: 2
aaaaaa: 1
aaa我們的贏家也是如此，出現了 3 次 * 長度 4 是 12。是的，aaaa得分也是 12，但排aaa在第一位。
我已經嘗試了我知道或可以弄清楚的唯一方法，但是我有一個長度為 100,000 的輸入字串，并且只找到所有子字串是 O(n^2)，這會掛起我的程式：
var theSet = new HashSet<string>();
for (int i = 1; i < source.Length; i )
{
for (int start = 0; start <= source.Length - i; start )
{
var sub = source.Substring(start, i);
if (!theSet.Contains(sub))
{
theSet.Add(sub);
}
}
}
...
// Some not-noteworthy benchmark related code
...
int maxVal = 0;
foreach (var sub in subs)
{
var count = 0;
for (var i = 0; i < source.Length - sub.Length 1; i )
{
if (source.Substring(i, sub.Length).Equals(sub)) count ;
}
if (sub.Length * count > maxVal)
{
maxVal = sub.Length * count;
}
}
我知道我正在尋找一種相對未知的演算法和/或資料結構，因為谷歌沒有產生與問題密切匹配的結果。事實上，在 Google 上我基本上只找到了我在上述代碼中嘗試使用的昂貴演算法。
uj5u.com熱心網友回復：
編輯：剛剛意識到問題在 GFG 上有解決方案：https : //www.geeksforgeeks.org/substring-highest-frequency-length-product/
這可以通過應用三種眾所周知的演算法在 O(n) 時間內解決：后綴陣列、LCP 陣列和直方圖中的最大矩形區域。
我不會提供任何代碼，因為這些演算法的實作很容易在 Internet 上找到。我將假設輸入字串是“banana”并嘗試解釋這些步驟及其作業原理。
1.運行后綴陣列 - O(n)
后綴陣列演算法按字母順序對字串的后綴進行排序。對于輸入“banana”，輸出將是陣列[5, 3, 1, 0, 4, 2]，其中 5 對應于從位置 5 開始的后綴（“a”），3 對應于從位置 3 開始的后綴（“ana”），1 對應于從位置 1 開始的后綴（“anana”）等。在我們計算這個陣列后，計算子串的出現次數變得容易得多，因為相等的子串是連續放置的：
- 一個
- 安娜
- 安娜
- 香蕉
- 吶
- 娜娜
例如，通過查看上面串列中的第 2 和第 3 個后綴，我們可以立即看到子字串“ana”出現了兩次。類似地，我們可以通過查看第 5 個和第 6 個來說子字串“n”也出現了兩次。
2. 運行 LCP 陣列 - O(n)
LCP 演算法計算后綴陣列中每對連續后綴之間的最長公共前綴的長度。“香蕉”的輸出將是 [1, 3, 0, 0, 2] ：
- 一個
- ana // "a" 和 "ana" 共享前綴 "a"，長度為 1
- anana // "ana" 和 "anana" 共享前綴 "ana"，長度為 3
- 香蕉 // "anana" 和 "banana" 沒有前綴，所以 0
- na // "banana" 和 "na" 沒有前綴，所以 0
- nana // "na" 和 "nana" 共享前綴 "na"，長度為 2
現在，如果我們將 LCP 演算法的輸出繪制為直方圖：
x
x x
xx x
-----
01234
-----
aaabnn
nnaaa
aan n
na a
an
a
現在，這是主要觀察：直方圖中接觸 y 軸的每個矩形對應一個子串及其出現：矩形的寬度等于，s.count - 1高度等于s.length
例如，考慮左下角的這個矩形，它對應于子字串“a”。
xx
--
01
矩形的高度為 1，即"a".length，寬度為 2，即"a".count - 1。而我們需要的值 ( s.count * s.length) 幾乎就是矩形的面積。
3. 找到直方圖中最大的矩形 - O(n)
現在我們需要做的就是在直方圖中找到最大的矩形來找到問題的答案，簡單的細微差別是在計算矩形面積時，我們需要在其寬度上加 1。這可以通過 1在演算法中的面積計算邏輯中簡單地添加 a 來完成。
對于“香蕉”示例，最大的矩形如下（考慮到我們為每個矩形的寬度添加了 1）：
x
x
x
-
1
我們將其寬度加 1 并將其面積計算為2 * 3 = 6，它等于子串“ana”出現的次數乘以它的長度。
3 個步驟中的每一個都花費 O(n) 時間，總時間復雜度為 O(n)。
uj5u.com熱心網友回復：
盡管不是非常有效的 O(n) 復雜度，但這確實有效。我無法想象更有效的方法......
static void TestRegexes()
{
var n = CountSubs("aaaaaa", "a");
var nn = CountSubs("aaaaaa", "aa");
var nnn = CountSubs("aaaaaa", "aaa");
var nnnn = CountSubs("aaaaaa", "aaaa");
var nnnnn = CountSubs("aaaaaa", "aaaaa");
var nnnnnn = CountSubs("aaaaaa", "aaaaaa");
;
}
private static int CountSubs( string content, string needle)
{
int l = content.Length;
int i = 0;
int count = 0;
while (content.Length >= needle.Length)
{
if (content.StartsWith(needle))
{
count ;
}
content = content.Substring(1);
i ;
}
return count;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400695.html
上一篇：Java中的等價排序二叉樹