CODEWITHSUNDEEP
stringalgorithmsearchpattern-matching
user973888
user973888

Reputation:

KMP algorithm for multiple occurrences

Is it possible to still perform a O(n) time complexity to search multiple occurrences of Knuth–Morris–Pratt algorithm?

Upvotes: 3

Views: 1898

Answers (1)

Narek Saribekyan
Narek Saribekyan

Reputation: 175

Suppose we have a string S[0,...,N]. Recall that the ith entry in the prefix array stores the length of the maximal prefix of S[0,...,i] that matches the suffix. We can calculate the prefix array P for pattern$subject (assuming that $ doesn't occur in subject). It remains to find indices such that P[i]==length(pattern), which can be done in linear time.

Upvotes: 2

Related Questions