fast_grep
Updated on
•
by - pranav
categories - backend
** I will also write a post in TMB regarding the algorithm. **
KMP algorithm is one of the famous algorithms for pattern matching. And I had to find a lot of resources to find what all was happening in the algorithm, and when I finally understood it, I had to give a try to the implementation of the algo. Since KMP works in a DFA fashion, it was easy to integrate it into system which reads a large file in a window, character by character updating it (saves a lot of memory), and thscans the window to change states of the DFA array of KMP. Hence it performs well and produces faster results than native grep in a specific case of displaying before and after characters of the pattern.
The following code is the computation function of KMP, which populated the kmp array. Head over to the repository for more details.
