shimengwang/cpp-string-matching

String Matching in C++

Introduction

This is a very simple string matching algorithm written in C++ that uses a finite state machine and a trie to do the matching. Furthermore this is only a weekend project that I hacked on some time ago and never published it, until now.

String Matching Algorithm

This implementation is based on the original paper published on 1975.

I am using the BFS (Breadth First Search) strategy when building the failures for the string matching index, so I am visiting the neighbours before visiting the child nodes using a queue as presented in the original paper.

How the string matching is being performed is best represented in the diagram below taken from the slides by Pekka Kilpeläinen

Trie

You'll find the simplest Trie implementation.

Trie has an ordered tree data structure so in our case it will keep adding characters until it reaches the end of the string that we passed. In the end our tree will look like the diagram below for strings like corvo, hey, his and hers, that's my goal for now but I will keep changing it. You can check the usage in the main.cpp file.

Trie diagram is taken from the same slides as the Aho Corasick diagram.