aybek.b5's blog

By aybek.b5, 5 years ago, translation, In English,

Hi. I'm beginner at competitive programming and there is 100% that this topic is not original, but, in spite of this, I decided to publish it. So, (you are still reading, that's achievement for me :D). Sometimes we need to associate string with some object and then quickly find it by those key string. Prefix trees are good thing to do it. For more information about them read this, or this.

Algorithm complexities:

Add element O(1) // iterations are equal to length of string

Remove element O(1)

Search element O(1)

Memory: In worse case each bound's weight is 300 bytes, but you can reduce this by using function to get child id by character (see in code), and saving pointer to object you are pushing.

Need a more detailed analysis, but, in generally we can see that this structure is very fast, but not so effective in memory usage, you can use it when you are need to balance memory and time.

Here is realization, hope some will use in their solution:

template <class T, std::size_t ALPHA_SIZE>
class prefix {
        public:
		prefix(std::size_t (* f)(char))
			: I(f), m_root(new node)
		{}

		~prefix() {
			rec_del(m_root);
		}

		T & operator[] (std::string s) {
			node * curr = m_root;
			for (auto e: s) {
				size_t i = I(e);
				if (curr->next[i] != nullptr) {
					curr = curr->next[i];
				} else {
					curr = curr->next[i] = new node;
				}
			}
			curr->used = 1;
			return curr->val;
		}

		bool thereis(std::string s) {
			node * curr = m_root;
			for (auto e: s) {
				size_t i = I(e);
				if (curr->next[i] != nullptr) {
					curr = curr->next[i];
				} else {
					return 0;
				}
			}
			return curr->used;
		}

	private:
		struct node {
			T val;
			uint8_t used;
			node * next[ALPHA_SIZE];
			node(): used(0) {
				for (size_t i = 0; i < ALPHA_SIZE; ++i)
					next[i] = nullptr;
			}
			~node() {}

		} * m_root;
		std::size_t (* I)(char);

		void rec_del(node * curr) {
			if (curr == nullptr) {
				return;
			} else {
				for (size_t i = 0; i < ALPHA_SIZE; ++i)
					rec_del(curr->next[i]);
			}

			delete curr;
		}
};

And this is test program.

#include <iostream>
#include <cassert>
#include <cstdio>
#include <string>

#include "prefix_tree.hpp"

inline std::size_t iofc(char c) {
	return static_cast<std::size_t>(c);
}

int main() {
	using namespace std;

	tree::prefix<int, 127> tree(iofc);

	tree["hello this is where you are!"] = 2;

	assert(tree.thereis("0000000000000000000000000000") == 0);
	assert(tree.thereis("hello this is where you are!") == 1);


	return 0;
}

Yes, many useful functions are absent, (such as remove for example, iterators). But the first step is made, so, let's improve it, good luck and have fun!

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

As far as I know, your code is about Trie, not Suffix tree. +1 for your contribution.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Yes, you are right, I mixed prefix trees with suffix )

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't see anything related to "suffix". You may need to change the title into "Prefix trees".

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide a good resource to learn about this data structure?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You may want to notice some things about your complexity: 1) When you add or delete a string the complexity is not O(1), but O(size of the string, that you add / delete) 2) When you search for a string the worst case leads is O(size of the string, that you search for)