Any good methods to optimize memory usage for maximum line input length

Question

I am developing a string algorithm, and the problem is the size of the input. By definition, the maximum Java string length is 2147483647 to avoid confusion ~ 2.15x10 ^ 9.

The Manacher algorithm requires, by definition, an array of characters:

char[n*2 +3] where n is the input length (string of size n)

By definition, the maximum integer is the above ~ 2.15x10 ^ 9, so an array of characters can have a maximum size

char [ ~2.15x10^9 ];

This calculation of the manachers algorithm in java reduces the limit of the input string to n = (~ 2.15x10 ^ 9 - 3) / 2. To be precise, this is exactly 1073741822. ~ 1.1x10 ^ 9.

A char array of maximum length has (n * 2) + 32 bytes = (~ 2.1x10 ^ 9 * 2) + 32 bytes = ~ 4.2x10 ^ 9 bytes (4.2GBs)

Theres additional arrays of various sizes, sets and other collections. I believe that this made the program take up the whole space of ~ 30 GB. for maximum input of RAM for calculating an algorithm that, as we have determined, does not exceed ~ 1.1x10 ^ 9 characters.

Could you advise me on some technique to keep things even between the “Longest possible line input” and “Memory management”? Thanks you

Answer 1

In accordance with this article, the Manacher algorithm finds the longest palindromic substring in linear time (s n, which is the length of the original string).

Java, , ( , ints, , ).

, , , ..

, 7 : A C T G, (, #) (, $ @). , 3 , . , , 21 long ( , long 64 ). , .

. , , , int .. , , , . ++. !