Using Python, created an algorithm inspired by Rabin-Karp Algorithm for string pattern matching in linear time. It works in linear time as the singular for loop runs O(n-m+1) simplified to O(len(str)). Since I create a set of all possible substrings of length of possible pattern and According to Python wiki: Time complexity, a set is implemented as a hash table. So you can expect to lookup/insert/delete in O(1) average.
-
Notifications
You must be signed in to change notification settings - Fork 0
Using Python, created an algorithm inspired by Rabin-Karp Algorithm for string pattern matching in linear time
License
ynd24/String-Pattern-Matching-Linear-Time
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
About
Using Python, created an algorithm inspired by Rabin-Karp Algorithm for string pattern matching in linear time
Topics
Resources
License
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published