Efficient String Matching Algorithm Based on Weak Factor Recognition
"Explore a simple yet highly efficient string matching algorithm leveraging weak factor recognition and hashing techniques. Discover how this algorithm outperforms existing solutions in various conditions, offering flexibility and improved running times. Dive into the theoretical framework and practical applications discussed in the research paper presented at the Prague Stringology Conference."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Speeding Up String Matching Speeding Up String Matching by Weak Factor Recognition by Weak Factor Recognition Domenico Cantone , Simone Faro , and Arianna Pavone Proceedings of the Prague Stringology Conference 42-50 August 28 30, 2017, Czech Technical University, Prague Presenter Kuan-Lin Lai Date: 2018/12/17
Abstract(1/2) Abstract(1/2) String matching is the problem of finding all the substrings of a text which match a given pattern. It is one of the most investigated problems in computer science, mainly due to its very diverse applications in several fields. Recently, much research in the string matching field has focused on the efficiency and flexibility of the searching procedure and quite effective techniques have been proposed for speeding up the existing solutions. In this context, algorithms based on factors recognition are among the best solutions.
Abstract(2/2) Abstract(2/2) In this paper, we present a simple and very efficient algorithm for string matching based on a weak factor recognition and hashing. Our algorithm has a quadratic worst-case running time. However, despite its quadratic complexity, experimental results show that our algorithm obtains in most cases the best running times when compared, under various conditions, against the most effective algorithms present in literature. In the case of small alphabets and long patterns, the gain in running times reaches 28%. This makes our proposed algorithm one of the most flexible solutions in practical cases.
Weak Factor Recognition: Hash Hash all substring of pattern Time: O(m2) Space: O(2 ) x = ATATCCG => ( A, AT, ATA, , ATATCCG ), (T, TA, TAT, , TATCCG), , (G)
Searching Phase search
Experiment Experiment
Experiment Experiment
Experiment Experiment
