Categories > Etc > Software & Hardware >

# KMP algorithm's time complexity

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)?

Replied

pov: robloooc forum

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

Cancel

Post

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.

Cancel

Post

### Users viewing this thread:

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

Cancel

Post