# How use generalized suffix tree to match prefix string?

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?

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