Show HN: I created a (hopefully fast) C++ lib to find words in ASCII sequences

4 points by waffenklang 6 years ago | 2 comments

Hi,

to provide a bit context, I'm the author of a small causal android game called "Squabbel"[1] which is a modern take on a merge of tetris and scrabble.

Its core is based around the idea to find strings within a sequence of characters, which is accomplished by using a deterministic finite automaton.

Currently I'm working on the successor of Squabbel and I was optimizing the internal search engine and refactored the code to a c++ library which is now available on github

https://github.com/0x10/fastdict

The search times are to my needs pretty good and I would love to get some feedback on the performance.

Thanks.

[1] https://play.google.com/store/apps/details?id=cc.deadlock.squabbel.lite

rogaos 6 years ago |

Cool! Seems similar to the Aho-Corasick algorithm, which was designed for exactly this task (https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm)

waffenklang 6 years ago | |

Wow.. I'm a bit ashamed as I searched for algorithms on that topic but was obviously unable to get the right keywords to find that one. Thanks for pointing it out. I will look into that one more deeply, but on the first glance its basically the same algorithm.