我正在设计一个字符串算法，问题在于输入的大小。根据定义，Java 的最大字符串长度为 2147483647，以避免混淆 ~2.15x10^9。
根据定义，Manacher 的算法需要一个字符数组:
char[n*2 +3] 其中 n 是输入的长度(大小为 n 的字符串)
根据定义，最大整数是上面提到的 ~2.15x10^9，因此字符数组可以是最大大小
char [ ~2.15x10^9 ];
在 java 中计算 manachers 算法，将输入字符串的限制降低到 n = (~2.15x10^9 - 3)/2 。准确地说，就是 1073741822。~1.1x10^9。
最大长度的 char 数组有 (n*2) + 32 个字节 = ( ~2.1x10^9 * 2 ) + 32 个字节 = ~4.2x10^9 个字节 (4.2GB)
还有各种大小的数组、集合和其他集合。我相信这将使程序占用 ~~30GB 的整个空间。用于算法计算的 RAM 内存的最大输入，我们确定其长度最多为 ~1.1x10^9 个字符。
你能给我一些建议，让事情在“最长可能的字符串输入”和“内存管理”之间保持平衡吗？谢谢
最佳答案
根据 this article ，Manacher 算法在线性时间 内找到最长的回文子串(n 为原始字符串的长度)。
Here's an implementation in Java ，这表明该算法在内存消耗方面也相当出色(您需要两个数组，一个 chars 和另一个 ints，两者的长度都是原始字符串的两倍，并且您还需要存储原始字符串)。
问题是您的原始字符串非常长，因此您达到了语言限制、内存限制等。
另一方面，您的字母表仅由 7 个字符组成:您的原始字符串字符 A C T G，加上字母分隔符(例如 #)以及开始和结束字符串字符(例如 $ 和 @)。这意味着您只需要3 位 来存储每个可能的字符。因此，如果您愿意使用按位运算符 和位掩码，您可以将21 个字符存储在long (这是因为 long 是用 64 位表示的)。这种方法的代码会更复杂，但会使用更少的内存。
另一种可能的解决方案是使用动态结构而不是字符串和数组。这些结构将使用大量内存，但不会是连续内存，这意味着您不会达到最大数组大小限制和整数的语言限制等。这种方法使用 suffix tree , 根据this article , 是一种线性时间方法。在那篇文章中有一个 C++ 的解决方案。祝你好运!
关于java - 任何用于最大字符串输入长度的内存使用优化的好技术，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43352433/