You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in suffix tree implementation(WA)

code : https://ideone.com/ZUfpWX

prob : https://www.hackerearth.com/practice/data-structures/advanced-data-structures/suffix-trees/tutorial/ (practice prob).

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

pk301's gravatar image

2★pk301
62710
accept rate: 16%

edited 21 Jan '18, 09:40

please help me.

(20 Jan '18, 21:00) pk3012★

Sorry dear, looked just now. Will look into it.

(21 Jan '18, 00:29) vijju123 ♦♦5★

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 ♦♦5★

@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★

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 :/ )

link

answered 21 Jan '18, 20:23

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 21 Jan '18, 20:24

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) vijju123 ♦♦5★
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) vijju123 ♦♦5★

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) vijju123 ♦♦5★

thanks! :)

(23 Jan '18, 15:05) pk3012★
showing 5 of 8 show all
toggle preview
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