Will Rope Data Structure work on the problem String Query in April '13??
And is there any good tutorial on it??
3 Likes
Dynamic Extended Suffix Arrays should do the job too.
Unfortunately I didn’t have time to implement it properly.
3 Likes
@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…
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
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 .
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.
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.
Hi all.
Sorry for delay with the editorial for STRQUERY.
This weekend was full of contests - I’ve participated in 6 
Hence only brief editorial for INVBINCF was prepared and no for STRQUERY.
This problem is quite tough and explaining it properly requires some time.
I spend a lot of time only to understand the solution having some short abstract present in author’s code.
Now I completely understand @winger solution and if you wait for one day I will present you a very good editorial so that anyone could understand and implement the solution.
In short, the solution uses dynamic suffix array that supports modification operations at the beginning of the string and count queries. This is achieved by using special balanced binary search tree and it is the toughest part of the problem. Let’s call this data structure as suffix stack.
Then the actual problem can be solved by using 4 suffix stacks - we divide the string into 4 nearly equal pieces such that each modification is performed at the beginning of one of the pieces (two of them are reversed). Also sometimes we should completely rebuild two neighboring suffix stacks (when one of them becomes empty). But this happens only O(log Q) times (the reasoning is the same as in the implementation of disjoint set data structure with linked list).
Also we should count occurrences of query string at the boundary of neighboring pieces. But this is simple. If we have two strings A and B and want to count the number of those occurrences of the string C in concatenation A + B that touch both A and B we create string D of the size at most 2 * |C| by concatenating suffix of A of size min(|A|,|C|-1) and prefix of B of size min(|B|,|C|-1) and then count number of occurrences of C in the string D using any standard algorithm like KMP, Z-Algorithm or hashing in O(|C|+|D|) = O(|C|) time.
It seems that among AC solutions there are many different ideas for mentioned above data structure that supports only modification queries at the beginning, so editorial will cover only one possible solution.
Regards,
Anton.
UPD
Finally editorial is ready. It is THE LONGEST editorial ever. Check it out here.
8 Likes
What is rope data structure?
ya that one…
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.
Ya… I searched a lot… The best description I could find was on wikipedia…
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.
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.
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
Thats like huge… but anyways thanx…
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. good luck
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???