KMP string matching algo

#1

why do we have to make kmpreprocessor function,the question is to find pattern matching string then why cannot we just execute kmpsearch function,what is the need to make reset table for pattern string

#2

Simply because the reset table tells u at every index what is the length of the longest suffix present till now which is also a prefix in the pattern , basically

While traversing the text string when we find a mismatch after a certain point we can refer to the reset table to move back to that index of the pattern in case if prefix exists , else we are directed to the 0th index directly,This enhances the search by not iterating from a previous point in the text string.

Reset table gives u a index to refer to incase of mismatch so that the search does not have to begin from the first index of pattern, and no back traversal is required in the text string also.

#3

This can be done by reset table in KMPsearch,what is the need to make 2 reset table?

#4

Its just 1 reset table defined globally.
it is being initialized -1 in the KMP search function but it initialized in the pre-processor function. which is later used in the KMPsearch function.

So basically just 1 reset table is being used.

#5

it is not clear,could you elaborate a little more how is the code working

#6

in terms of flow of the program, there is a reset table which is first initialised with position of prefix in the preproccessor function…
Then in the kmp-function…
for the pattern
A B A B C A B A B
the reset table becomes: 0 0 1 2 0 1 2 3 4
The reset table is made in this way
we start iterating the string of text -
start comparing the occurrence of pattern in text, in case of mismatch the reset table is refered to the the pointer to the pattern is moved to a previous position in case that substring is present as a prefix.
if the pointer reached end of the pattern string, then we found a match,

else continue to iterate.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.