String datastructure supporting append, prepend and search operations

Question

I need to build a text editor as my mini project, and I need to design a data structure or algorithm that supports following operation:

• Append : Append a character at the end of the String.
• Prepend : Prepend a character at the beginning of the string.
• Search : Given a search string s, find all the occurrences of the string.

Each operation in O(log n) time or less. Search and replace operations will be appreciable but not necessary. The maximum length of string is constant. Any ideas how to achieve this?

Thanks!

Answer 1

A common data structure for this kind of application is a Rope, where Append and Prepend are O(1), although that depends a bit on whether the tree is balanced. However, as noted by Толя, Search would be linear.

There are certainly data structures that can make the search faster, such as a Suffix Tree, but they are probably not appropriate for a text editor application.

Answer 2

I would propose you adapt a Trie. On an append operation add all the suffixes of the string ending at the new character with length up to the maximum length of the string in the datastructure. On prepend add all the prefixes of the string starting at the new char with length up to the fixed length of the string. Asymptotically both operations are constant - they take O(k^2) where k is the fixed length of the string. For each node in the structure keep track of all the strings ending at that node(possibly a list).

A search operation will again be constant: iterate over the string and output all indexes stored in the ending node(if you have not "dropped out the tree").

A drawback of my approach is the memory overhead(at most times the maximum length of a word), but if the maximum string length allowed is reasonable and you only insert real words(from English dictionary for instance), this should not be a big problem.