I know that generalized suffix tree can match substring for a given pattern. But I have need a data structure which is able to

  1. match prefix of many strings.
  2. match sub string of of many strings.

For example: The strings I have:

abc, abcd, bcxabc,

If the pattern is abc, I should match all three strings.

If the pattern is ^abc, I should only match abc, abcd. The ^ represent the start of a string.

I know I can build another TRIE. But it will cost almost the same space.

If there any way to achieve this in generalized suffix tree?

  • 2
    $\begingroup$ Hint: Introduce a new alphabet symbol which represents the start of a string (the caret symbol in your example). $\endgroup$ – Pseudonym Dec 26 '18 at 7:42
  • $\begingroup$ You mean when I build the suffix tree? Yeah, that's also a trick. $\endgroup$ – worldterminator Dec 26 '18 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.