CODEWITHSUNDEEP
stringalgorithmfunctionperformancepattern-matching
Chris
Chris

Reputation: 26888

KMP's failure function

I've recently learnt the KMP string matching algorithm, and I almost get all of it. But what I don't get is how to build the failure function in O( length_of_pattern ). I don't need code, I need a clear explanation if possible. Thanks in advance!

Upvotes: 2

Views: 2905

Answers (1)

Ricky Bobby
Ricky Bobby

Reputation: 7608

from this site:

The KMP algorithm preprocess the pattern P by computing a failure function f that indicates the largest possible shift s using previously performed comparisons.

Specifically, the failure function f(j) is defined as the length of the longest prefix of P that is a suffix of P[i . . j].

Here is a pseudo code for the construction, I guess you can get the detail of the explaination on the site 

        KNUTH-MORRIS-PRATT FAILURE (P)

            Input:    Pattern with m characters
            Output: Failure function f for P[i . . j]

            i ← 1
            j ← 0
            f(0) ← 0
            while i < m do    /// your complexity will be O(length of pattern)
                if P[j] = P[i]
                    f(i) ← j +1
                     i ← i +1
                      j← j + 1
                else if (j != 0)
                     j ← f(j - 1)
                else
                    f(i) ← 0
                    i ← i +1

Hope it answers your question

Upvotes: 2

Related Questions