Forums
New posts
Search forums
News
Security News
Technology News
Giveaways
Giveaways, Promotions and Contests
Discounts & Deals
Reviews
Users Reviews
Video Reviews
Support
Windows Malware Removal Help & Support
Mac Malware Removal Help & Support
Mobile Malware Removal Help & Support
Blog
Log in
Register
What's new
Search
Search titles only
By:
Search titles only
By:
Reply to thread
Menu
Install the app
Install
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
Guides
Programming Guides & Questions
KMP algorithm to find a specific pattern
Message
<blockquote data-quote="quentisa" data-source="post: 1020567" data-attributes="member: 98424"><p>I'm trying to implement the KMP algorithm to find a specific pattern within a larger string, but I'm having trouble understanding how to implement the search function properly. I've got the partial match table construction working correctly, but when I try to use it in the search function, the algorithm is not returning the correct results. I've tried going through the documentation and examples like <a href="https://www.scaler.com/topics/data-structures/kmp-algorithm/" target="_blank">this</a>, but I'm still not sure what I'm doing wrong.</p><p>Here's an example of the code I've written for the search function:</p><p>[CODE]def kmp_search(text, pattern, partial_match_table):</p><p>n = len(text)</p><p>m = len(pattern)</p><p>j = 0</p><p>for i in range(n):</p><p>while j > 0 and text[i] != pattern[j]:</p><p>j = partial_match_table[j - 1]</p><p> if text[i] == pattern[j]:</p><p>j += 1</p><p> if j == m:</p><p>return i - j + 1</p><p>return -1[/CODE]</p><p>I'm not sure if there's a mistake in this code or if I'm not understanding how to properly use the partial match table in the search function. I would really appreciate any help in understanding how to correctly implement the search function so that the KMP algorithm can work properly.</p></blockquote><p></p>
[QUOTE="quentisa, post: 1020567, member: 98424"] I'm trying to implement the KMP algorithm to find a specific pattern within a larger string, but I'm having trouble understanding how to implement the search function properly. I've got the partial match table construction working correctly, but when I try to use it in the search function, the algorithm is not returning the correct results. I've tried going through the documentation and examples like [URL='https://www.scaler.com/topics/data-structures/kmp-algorithm/']this[/URL], but I'm still not sure what I'm doing wrong. Here's an example of the code I've written for the search function: [CODE]def kmp_search(text, pattern, partial_match_table): n = len(text) m = len(pattern) j = 0 for i in range(n): while j > 0 and text[i] != pattern[j]: j = partial_match_table[j - 1] if text[i] == pattern[j]: j += 1 if j == m: return i - j + 1 return -1[/CODE] I'm not sure if there's a mistake in this code or if I'm not understanding how to properly use the partial match table in the search function. I would really appreciate any help in understanding how to correctly implement the search function so that the KMP algorithm can work properly. [/QUOTE]
Insert quotes…
Verification
Post reply
Top