CODEWITHSUNDEEP
stringalgorithmstring-search
Nithin Jain
Nithin Jain

Reputation: 1

Trying to get prefix table for the pattern in KMP algorithm

I'm trying to implement KMP algorithm for string matching, basically i have my pattern tenen which needs to be searched in a specific string lets assume that string to be this is ten in tenen.

I'm trying to write pseudo code for creating prefix table of my pattern. I want to understand what would be the prefix table for the pattern tenen and also if i can get the explanation of how we came to the result, that would be great.

Upvotes: 0

Views: 137

Answers (1)

Nur
Nur

Reputation: 2473

Description of pseudocode for the search algorithm, from wikipadia.

algorithm kmp_search:
    input:
        an array of characters, S (the text to be searched)
        an array of characters, W (the word sought)
    output:
        an array of integers, P (positions in S at which W is found)
        an integer, nP (number of positions)

    define variables:
        an integer, j ← 0 (the position of the current character in S)
        an integer, k ← 0 (the position of the current character in W)
        an array of integers, T (the table, computed elsewhere)

    let nP ← 0

    while j < length(S) do
        if W[k] = S[j] then
            let j ← j + 1
            let k ← k + 1
            if k = length(W) then
                (occurrence found, if only first occurrence is needed, m ← j - k  may be returned here)
                let P[nP] ← j - k, nP ← nP + 1
                let k ← T[k] (T[length(W)] can't be -1)
        else
            let k ← T[k]
            if k < 0 then
                let j ← j + 1
                let k ← k + 1

Upvotes: 0

Related Questions