×

# Help in suffix tree implementation(WA)

 0 I am getting wrong answer for last 2(UPD : 3days lol) days. Didn't able to find the bug! please help. In simple words Ques just asked to sort all the suffix and print at which index suffix with sortedIndex 'j' starts! My approach : i have just created a suffix tree and then just do a dfs on the tree and keep counts of number of indexes visited(end_Of_Curr_Node - start_Of_Curr_Node + 1) upto the current node. Now, as we reach leaf node(as we have inserted a unique '$' character so, all the suffixes must end in root) we have the count of the number of indices visited and to get the index of the suffix in the original string we just subtract it by lenghtOfString. Why I think that this is correct? : I start doing dfs from '0' to '255' and so ensures that we visit each valid suffixes in lexographical order and so, the first reached leaf is the one which comes first when we sort all the substrings! asked 20 Jan '18, 00:26 2★pk301 627●10 accept rate: 16% please help me. (20 Jan '18, 21:00) pk3012★ Sorry dear, looked just now. Will look into it. (21 Jan '18, 00:29) It will take time. I will have to understand the complete article so that I can make sense of the question. Can you explain the question in simpler terms, along with what you did? (21 Jan '18, 00:49) @vijju123 i have added a short explaination. Please comment if you didn't understand any section of code. (21 Jan '18, 09:41) pk3012★ @vijju123 please reply something.. (21 Jan '18, 18:26) pk3012★ One Answer:  1 Check your output for this case- Input abaaaab Your output 2 3 0 4 6 1 5  I am expecting 2 3 4 5 0 6 1 as the output, because substring starting from index 0 is "abXXX" while substring from index 4 and 5 are "aab" and "ab". And I expected index 1 to be last as it started with b. I am sorry I took so much time, it isnt easy to debug because of lack of correct code, and my understanding of that question. I have to test all the input and your output with pen and paper (wont be surpirsed if I committed error here :/ ) answered 21 Jan '18, 20:23 15.4k●1●20●66 accept rate: 18% thanks a lot for this! Now, i edited the code and it is almost correct(now printing (n-2) outputs for some inputs) : https://ideone.com/4oaxnR last time please look into it :) (22 Jan '18, 02:00) pk3012★ Can you share the input? (Assuming they arent those hugeeee TCs XD) (22 Jan '18, 02:03) 1 Here- Input aaabaaaaa Your Output 9 7 (My debugging statements- Size of string Size of your answer) 8 5 4 0 1 2 3 (22 Jan '18, 02:29) thanks a lot! only add a line and AC :) AC code : https://ideone.com/4GxpU2 (23 Jan '18, 13:25) pk3012★ Btw if you have any small and clear implementation then please share! (23 Jan '18, 13:27) pk3012★ 1 I will give it a try and let you know! :) (23 Jan '18, 14:48) thanks! :) (23 Jan '18, 15:05) pk3012★ showing 5 of 8 show all  toggle preview community wiki: Preview ### Follow this question By Email: Once you sign in you will be able to subscribe for any updates here By RSS: Answers Answers and Comments Markdown Basics • *italic* or _italic_ • **bold** or __bold__ • link:[text](http://url.com/ "title") • image?![alt text](/path/img.jpg "title") • numbered list: 1. Foo 2. Bar • to add a line break simply add two spaces to where you would like the new line to be. • basic HTML tags are also supported • mathemetical formulas in Latex between$ symbol

Question tags:

×1,070
×239
×109

question asked: 20 Jan '18, 00:26

question was seen: 352 times

last updated: 23 Jan '18, 15:05