首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >任何用于优化最大字符串输入长度的内存使用的好方法

任何用于优化最大字符串输入长度的内存使用的好方法
EN

Stack Overflow用户
提问于 2017-04-11 17:19:36
回答 1查看 115关注 0票数 4

我正在设计一个字符串算法,问题在于输入的大小。根据定义,Java的最大字符串长度为2147483647,以避免混淆~2.15x10^9。

根据定义,Manacher的算法需要一组字符:

char[n*2 +3],其中n是输入的长度(大小为n的字符串)

根据定义,最大整数是上面提到的~2.15x10^9,因此一个字符数组可以是最大大小的。

代码语言:javascript
运行
复制
char [ ~2.15x10^9 ];

该算法在java中计算,将输入字符串的限制降低到n=(~2.15x10^9-3)/2。准确地说,那就是1073741822。~1.1x10^9。

最大长度的字符数组具有(n*2) + 32字节=( ~2.1x10^9 *2)+ 32字节= ~4.2x10^9字节(4.2GB)

还有不同大小、集合和其他集合的附加数组。我相信这将使程序占用整个空间~30 of。对于内存输入最大的算法,算法的计算长度最多为1.1x10^9个字符。

你能建议我一些技术,即使是在“最长可能的字符串输入”和“内存管理”之间?谢谢

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2017-04-11 19:00:28

根据这篇文章,Manacher算法在线性时间内找到最长的回文子串( n是原始字符串的长度)。

以下是Java的一个实现,它展示了该算法在内存消耗方面的优势(您需要两个数组,一个是字符,另一个是ints,它们的长度都是原始字符串的两倍,您还需要存储原始字符串)。

问题是原来的字符串非常长,所以您正在达到语言限制、内存限制等。

另一方面,您的字母表只包含7个字符:原始字符串字符A C T G,加上字母分隔符(如#)和字符串字符的开始和结束(如$@)。这意味着您只需要使用3位来存储每个可能的字符。因此,如果您愿意使用按位运算符和位掩码,您可以在一个long中存储21个字符(这是因为long用64位表示)。这种方法对代码来说可能更复杂,但它使用的内存要少得多。

另一个可能的解决方案是使用动态结构,而不是字符串和数组。这些结构将使用相当大的内存,但不会是连续内存,这意味着您不会达到最大数组大小限制和it语言限制等。这种方法使用https://en.wikipedia.org/wiki/Suffix_tree,根据这篇文章的说法,这是一种线性时间方法。在那篇文章中,有一个C++的解决方案。祝好运!

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/43352433

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档