Re: computer-go: help with a fast pattern matching utility requested

[Martin Moller Pedersen <tusk@xxxxxxxxxxx>]

-> Hi,
-> I'm writing a Go program that needs to match a given subsection of the 
-> board to a list of predefined patterns.  both are converted to strings, so 
-> it becomes a 1-d problem.  The program is in C/C++.
-> 
-> a DFA is really the only option I see, but the question is how to construct 
-> it? I considered using flex, but its not quite what i need - instead of 
-> matching multiple tokens on one input, i need to match the whole input 
-> string to one or several patterns (each time from the beginning of the 
-> input).  Flex/lex is much too big for what I need - ie much slower, and I 
-> was hoping for a way to add/subtract patterns from the DFA w/o completely 
-> rebuilding it, if possible.
-> I considered using GNUgo's matching mechanism - but its too tied to their 
-> implementation and it doesn't allow modifying the dfa w/o rebuilding it.
-> 
-> If anyone knows of a utility to do this in C, I would greatly appreciate 
-> letting me know.  Please email directly to mvp9@xxxxxxxxxxxxxxxxx
-> thanks,
-> Mike
-> 

Hi Mike,

I don't understand exactly what you are looking for but it sounds like
something like a "Suffix Tree".

Anyway, check these links:

http://www.nist.gov/dads/HTML/determFinitAutSrch.html
Contain some C-source for DFA.

http://www.cs.lth.se/~jesper/research.html
This guy knows a lot of string matching.

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix.html
Suffix Trees.

Good luck,
Martin M. Pedersen