我正在设计一个字符串算法,问题在于输入的大小。根据定义,Java的最大字符串长度为2147483647,以避免混淆~2.15x10^9。
根据定义,Manacher的算法需要一组字符:
char[n*2 +3]
,其中n是输入的长度(大小为n的字符串)
根据定义,最大整数是上面提到的~2.15x10^9,因此一个字符数组可以是最大大小的。
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个字符。
你能建议我一些技术,即使是在“最长可能的字符串输入”和“内存管理”之间?谢谢
发布于 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++的解决方案。祝好运!
https://stackoverflow.com/questions/43352433
复制相似问题