Help in suffix tree implementation(WA)

general
, ,
1

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!

2

please help me.

3

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

4

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?

5

@vijju123 i have added a short explaination. Please comment if you didn’t understand any section of code.

6

@vijju123 please reply something…

7

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

1 Like
8

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 :slight_smile:

9

Can you share the input? (Assuming they arent those hugeeee TCs XD)

10

It’s huge : https://he-s3.s3.amazonaws.com/media/hackathon/question-for-new-practice-section/problems/68924214-4-input-68923e7.txt?Signature=V0QWQ5pmwLa7YyV0GyfoSCfDLy8%3D&Expires=1516568044&AWSAccessKeyId=AKIAIDRXK3ZWDNTBIPQA

11

Here-


Input
aaabaaaaa
Your Output
9 7 (My debugging statements- Size of string Size of your answer)
8 5 4 0 1 2 3
1 Like
12

thanks a lot! only add a line and AC :slight_smile:

AC code : https://ideone.com/4GxpU2

13

Btw if you have any small and clear implementation then please share!

14

I will give it a try and let you know! :slight_smile:

1 Like
15

thanks! :slight_smile: