BullyWiiHacks
Welcome dear guest! Very Happy

To start posting and being part of the community, you simply need to register an account or log into an existing one.

Be sure to check out disposable e-mail services, in case you prefer using one for this site instead of your legit address: http://10minutemail.com/10MinuteMail/

If you do not wish to register at all, that's fine but there will be more advertisements. :/

You can see and download all content provided for regular members even without an account!

Your contributions will be greatly appreciated though, give it a shot and register today! thumbsup

Join the forum, it's quick and easy

BullyWiiHacks
Welcome dear guest! Very Happy

To start posting and being part of the community, you simply need to register an account or log into an existing one.

Be sure to check out disposable e-mail services, in case you prefer using one for this site instead of your legit address: http://10minutemail.com/10MinuteMail/

If you do not wish to register at all, that's fine but there will be more advertisements. :/

You can see and download all content provided for regular members even without an account!

Your contributions will be greatly appreciated though, give it a shot and register today! thumbsup
BullyWiiHacks
Would you like to react to this message? Create an account in a few clicks or log in to continue.
BullyWiiHacks

Gaming, Modding & Programming

Important reminders:

- Click *HERE* for advanced forum search or check out the text field below on the front page for Google before posting
- NO support via private message (use the forum)
- Write meaningful topic titles
Site Translation
Latest topics
Search
 
 

Display results as :
 


Rechercher Advanced Search

October 2021
MonTueWedThuFriSatSun
    123
45678910
11121314151617
18192021222324
25262728293031

Calendar Calendar

Country Statistics
Free counters!

You are not connected. Please login or register

Knuth-Morris-Pratt (KMP) Algorithm Tutorial

Go down  Message [Page 1 of 1]

SnB@BWH

SnB@BWH
Admin & Writer
The KMP algorithm is an algorithm in computer science for searching for ocurrences of matches to a specified word, being the pattern within a given list. Upon finding a partial match, the algorithm then can determine, possibly, where the next partial / full match could be, which avoids the searching of already matched characters.

Here is an example of how the algorithm works:

Let's say the pattern (word) is denoted by the variable W.
The given list (string) shall be S.
M is the position within W where the match shall begin.
And I denotes the character being examined for a possible match.

                      1                2
M: 0123456789012345678901234567
S: ABDFECADBCAEF FABCD CBDFFEAA
W: ADBC
I: ...

1 & 2 denotes the carrying over after 9. This just makes it shorter to reference.
M is the position of every character within S, including spaces.
W is the pattern we are trying to find within S.
I is the incrementation of finding a match. It stops at the end of the match, if one is found or or until S contains no more characters to be examined for matches, in other words: the search fails.

Now, I'll explain how this works:

What we are searching for is W within S. If a match is found on the first character, we increment I by +1, and move onto the next character in S, if it does not match, we set I to 0 and M to how far we have searched within S.

Now, let's run through S to find a match:

M: 0123456789012345678901234567
S: ABDFECADBCAEF FABCD CBDFFEAA
W: ADBC
I: 0123456789

There is no match at M - Position 0, so we increment I+1, and move onto the next.
Still no match.
We repeat incrementing I+1, until a we find the match AND no match proceeds after the character we had just matched.
Since we have found a full match at M - Position 9, we can check to see if there is another possible match, by further incrementing I+1. However, there is no need, since we have already found the match.
I has been incremented 10 times, and found at M - Position 9.

The search has succeeded!

This is how the Knuth-Morris-Pratt (KMP) algorithm works.
I hope you enjoyed this tutorial. Smile

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm


_________________
Knuth-Morris-Pratt (KMP) Algorithm Tutorial Simple10

Knuth-Morris-Pratt (KMP) Algorithm Tutorial LSTjSyD: SnB_BWH#2732

Knuth-Morris-Pratt (KMP) Algorithm Tutorial 12073310

Back to top  Message [Page 1 of 1]

Permissions in this forum:
You cannot reply to topics in this forum