Suffix Array Advanced
Back to Problem Solutions forum
Hi!
I am facing the following problem: Doing the step #4 ("Let us concatenate these extracted words with spaces into a single string (thus representing a large book"), compiuter is working about 10 minutes for input like 493100 104 the function which builds the String is like this: for(int s:LC){st+=List.get(s)+" ";} where List is acctuale our words.txt,LC is an arrayList with adrresses for words to be concatenated . So before i proceed to build Suffix Array i stuck with String concatination which last at least 10 minutes. Please suggest what is wrong here ?
Hi!
In Java you always fall into such trouble if you are trying to create string by repeating concatenation of small chunks. Strings are immutable so you are really creating new large objects on every iteration.
Use StringBuilder or StringBuffer for this.
Dear Admin :) There is a lot trash information on internet on how to build Suffix Array and almost 100 % it just fake and you go nowhere. Please suggest a good algortim to follow, at least the name. Thanks!
Again me :) Let me give you some data . For example for input 502700 350 we have a very long String (4 676 925 - length) Substring and storing somwhere of these new Strings does not work becaouse of heap space problem and plus time runnig, which probably 20 minutes at least. I guess should be an algoritm that avoid somehow the substring method and build SuffixArray without it,thus finishing step n#4 in this problem. I looked for a good algoritm in google but got nothing essential, just couple of names of algoritms and theories without a good ral example. My questions is: can you give the name of algoritm (a real one) or a hint to how build SuffixArray from such crazy long String like (4 676 925 - length) Thanks!