Timeline for A different approach to string pattern matching algorithm
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 1, 2021 at 11:41 | comment | added | Deepeshkumar | @kaya3 Hi, I have modified the algorithm as you have suggested. Please have a look and let me know your opinion. | |
| Aug 1, 2021 at 7:15 | comment | added | Miguel Alorda | @kelly-bundy Oh, I see now. So the idea is prefering to do some calculations instead of doing more comparisons. Also, thanks for the link! | |
| Aug 1, 2021 at 2:26 | comment | added | Deepeshkumar | @kaya3, Great suggestion! Thanks! | |
| Jul 31, 2021 at 22:10 | comment | added | kaya3 | Using the sum as a simple kind of rolling hash could in principle be an improvement on the naive algorithm, except you are calculating the sum of each substring independently, in the naive way. For there to be a potential performance benefit, the sum should be calculated using a moving window approach where you add the new character on the right of the window and subtract the character on the left of the window in order to move the window along by one without needing a loop over the whole window to recompute the sum. | |
| Jul 31, 2021 at 21:10 | comment | added | Deepeshkumar | @m-alorda Thanks for the review, will definitely follow the instructions. | |
| Jul 31, 2021 at 20:57 | vote | accept | Deepeshkumar | ||
| Jul 31, 2021 at 16:51 | comment | added | Kelly Bundy | "I do not see ..." - Because you don't compare the characters at all if the sum already doesn't match. Rabin-Karp is better than sum, though. | |
| Jul 31, 2021 at 16:34 | history | answered | Miguel Alorda | CC BY-SA 4.0 |