Categories > Etc > Software & Hardware >

KMP algorithm's time complexity

UlaDeia

Senior Developer

Posts: 14

Threads: 9

Joined: Jul, 2022

Reputation: 4

Posted

I'm attempting to implement strstr using the KMP method. This is the algorithm as described in Wikipedia & scaler topics. The temporal complexity of the KMP algorithm is O(n), where n is the length of the bigger string.

vector<int> KMP(string S, string K)
{
    vector<int> T(K.size() + 1, -1);
    vector<int> matches;

    if(K.size() == 0)
    {
        matches.push_back(0);
        return matches;
    }
    for(int i = 1; i <= K.size(); i++)
    {
        int pos = T[i - 1];
        while(pos != -1 && K[pos] != K[i - 1]) pos = T[pos];
        T[i] = pos + 1;
    }

    int sp = 0;
    int kp = 0;
    while(sp < S.size())
    {
        while(kp != -1 && (kp == K.size() || K[kp] != S[sp])) kp = T[kp];
        kp++;
        sp++;
        if(kp == K.size()) matches.push_back(sp - K.size());
    }

    return matches;
}

I'm not sure how the complexity of this algorithm is O. (n). Can somebody explain how this code's complexity is O(n)?

  • 0

Posts: 27

Threads: 1

Joined: Oct, 2022

Reputation: 0

Replied

pov: robloooc forum

 

uhh just make that kp thing like 7 and it wil be fix :--)

  • 1

Posts: 1

Threads: 0

Joined: Nov, 2022

Reputation: 0

Replied

There is a simple article (I mean as simple as it can be for KMP :) ). It exactly shows why search time complexity is O(n). You might want to take a look.

  • 0

Users viewing this thread:

( Members: 0, Guests: 1, Total: 1 )