/String-matching-algorithms-and-applications

Implementation of various string matching algorithms and their experimental analysis. Contains paper describing different string matching algorithms with their time and space complexities.

Primary LanguageC++

String-matching-algorithms-and-applications

This includes implementation of different kinds of string matching algorithms like:Naive algorithm,KMP algorithm,Bayer moore algorithm, using Trie data structure, Automaton matcher algorithm, Aho-corasick algorithm,Rabin Karp algorithm,approximation algorithms, etc.

I have also done exhaustive study on various kinds of string matching algorithms and their real-world applications.

For each algorithm, I described their algorithm,time complexities, and space complexities. I did analysis of different types of string matching algorithms on random text taken from Wikipedia and search for pattern in it. Then I conclude that which algorithm is best in which cases. I have also implemented the code of the algorithms and experimented it in different conditions.

All the detailed analysis is present in pdf attached with it. Please go through it, then you will come to know about various string matching algorithm and in experimental analysis section, you will find that which algorithm is best in which situation.

Input files are also attached in this repository.