Discussion @ 1269. Obscene Words Filter @ Timus Online Judge

AC :) (+)

Posted by Yu Yuanming 11 Jun 2005 15:38

You should build a trie, which to store the word.
1.Build the trie in reverse order
2.Make suffix links in BFS order.
3.Process the text

But my algo must read the text in reverse order,so it has to use more 2000K :(
Otherwise, 1500K is enough.

Re: AC :) (+)

Posted by Votjakov Roman[Barnaul] 7 Nov 2006 21:05

How many vertex did you use in your tree?

Re: AC :) (+)

Posted by Votjakov Roman[Barnaul] 7 Nov 2006 21:07

maxn? I have got ML 7!

Re: AC :) (+)

Posted by cactus 13 Jul 2007 16:39

Me,too! -_-b

Re: AC :) (+)

Posted by cactus 14 Jul 2007 14:42

Now I've solved it.
We can only record the char on the node, not the pointer.

Discussion of Problem 1269. Obscene Words Filter