具有给定函数值的子字符串最大出现次数的算法
我必须为给定字符串max(s.length * s.count)的任何子字符串s查找t，其中s.length是子字符串的长度，s.count是s在t中发生的次数。子字符串可能在t中重叠。
示例:对于字符串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不会产生与问题相匹配的结果。事实上，Google基本上只是在上面的代码中找到了我尝试使用的代价高昂的算法。
回答 2
Stack Overflow用户
发布于 2021-12-29 21:39:33
编辑：刚刚意识到这个问题在GFG：https://www.geeksforgeeks.org/substring-highest-frequency-length-product/上有一个解决方案
利用三种著名的算法：后缀数组、LCP阵列和直方图中的最大矩形面积，可以在O(n)时间内解决这一问题.
我不会提供任何代码，因为这些算法的实现可以很容易地在互联网上找到。我将假设输入字符串是“香蕉”，并试图解释这些步骤以及它们的工作方式。
1.运行后缀Array - O(n)
后缀数组算法按字母顺序排列字符串的后缀。对于输入“[5, 3, 1, 0, 4, 2]”，输出将是数组，其中5对应于从位置5 ("a")开始的后缀，3对应于从位置3 ("ana")开始的后缀，1对应于从位置1 ("anana")开始的后缀，等等。在计算这个数组之后，由于相等的子字符串是连续放置的，所以计算子字符串出现的次数变得容易得多：
- 一个
- 分析
- 阿纳娜
- 香蕉
- 不可用
- 娜娜
例如，我们可以通过查看上面列表中的第二个和第三个后缀，立即看到子字符串"ana“发生了两次。同样，我们可以说子字符串"n“也发生了两次，通过查看第5和第6。
2.运行LCP阵列- O(n)
LCP算法计算后缀数组中每个连续后缀之间最长的公共前缀的长度。“香蕉”的输出将是1，3，0，0，2：
- 一个
- ana // "a“和"ana”共有前缀"a"，长度为1
- anana // "ana“和"anana”共有前缀"ana"，长度为3
- 香蕉//“安娜”和“香蕉”没有前缀，所以0
- na //“香蕉”和"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来实现。
以“香蕉”为例，最大的矩形如下(考虑到我们在每个矩形的宽度中添加了+1 )：
x
x
x
-
1我们在其宽度中添加一个，并将其面积计算为2 * 3 = 6，这等于子字符串"ana“发生的次数乘以其长度。
这三个步骤中的每一个步骤都需要O(n)时间，总时间复杂度为O(n)。
Stack Overflow用户
发布于 2021-12-29 12:50:18
尽管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://stackoverflow.com/questions/70518770
复制相似问题
腾讯云开发者
