STRQUERY - Will rope work here?

general
, , , ,
1

Will Rope Data Structure work on the problem String Query in April '13??

And is there any good tutorial on it??

2 Likes
2

What is rope data structure?

3

Probably this one - http://en.wikipedia.org/wiki/Rope_(data_structure) , right?

4

ya that one…

5

This was exactly what i thought, but unfortunately i could not implement it or get any tutorial on it. There is a sgi library for it but how to implement it on my own still remains a mystery for me.

6

Ya… I searched a lot… The best description I could find was on wikipedia…

7

when i searched for strquery i got something called “Generalized suffix tree” which can support all given operations in specified limits.But i didn’t get some working code of it.Seems like same thing
is implemented in @winger’s solution.

8

Dynamic Extended Suffix Arrays should do the job too.

Unfortunately I didn’t have time to implement it properly.

http://www-igm.univ-mlv.fr/~lecroq/articles/jda2009.pdf

1 Like
9

@cyberax: The thesis is really helpful… Will certainly implement it sometime…
But still it would be really helpful if in addition to above algorithm, I could get some help with Rope Data Structure…

10

what kinda help do you need ? as far as I understand the wiki page, it’s a specific kind of binary tree. you could find possible implementations in common languages in the external links section.

11

@cyberax: implementation was what I couldn’t find anywhere…

12

as i told you, external links in the wiki page :

http://gcc.gnu.org/onlinedocs/libstdc++/libstdc+±html-USERS-4.3/a01984.html

1 Like
13

Thats like huge… but anyways thanx…:slight_smile:

14

yeah, i thought the same. you could probably start from scratch, simply designing a binary tree, and then add method by method the features of ropes. i mean, if i were you, i would probably do that, because i understand better when i implement myself. :slight_smile: good luck

15

yeah,i got the same paper initially(when i was trying with suffix arrays) but never get any working code for “Dynamic Extended Suffix Arrays” or “Generalized suffix tree”.Can you provide me some???

16

Oh, It has a paper? Actually I made this problem myself.

And also I failed to prevent O(n^1.5) solution from getting Accpected, maybe It could be Online query or even past-time query.

1 Like
17

I have to admit codechef guys are putting some very good and tough real life problems these days like this one which could pave way for an efficient algos in text editors .

18

will this suffice? here

19

i used double link list to solve this problem. but it constantly showed run time error TLE WA … don’t know whats exact problem. as the problem had 150000 alphabets so i too had to dynamically allocate memory… i think cause of this much of memory ,it was showing random errors … if u guys have any idea then please tell me.

20

How about using a Doubly Linked List for this problem.

  • Each node will correspond to a character in String.
  • Maintain Head, Tail and Middle pointers.
  • Each type of INSERT/DELETE operation can be done in O(1) time.
  • To query, Convert the Doubly Linked List to a Char Array and use KMP algorithm.

I had tried this logic in Java but was getting a Runtime error. Please share your thoughts if it is a reasonable approach.