# KMP Algorithm
*Knuth-Morris-Pratt Algorithm*
Leetcode Problem:
* [28. Implement strStr()](https://leetcode.com/problems/implement-strstr/)
* [459. Repeated Substring Pattern](https://leetcode.com/problems/repeated-substring-pattern/)
* [686. Repeated String Match](https://leetcode.com/problems/repeated-string-match/)
#### c++ version:
```cpp
vector<int> lps(n,0);
for(int i=1,j=0;i<n;)
{
if(T[i]==T[j])
lps[i++]=++j;
else if(j==0)
i++;
else
j=lps[j-1];
}
```
#### python version
```python
i,j, lps = 1,0, [0]*n
while(i<n):
if(needle[i]==needle[j]):
j += 1
lps[i] = j
i += 1
elif(j==0):
i+=1
else:
j = lps[j-1]
```
Then we can use lps as Failure Function to solve these problems:
### 28. Implement strStr()
#### c++ version
```cpp
class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.size(), n = needle.size();
if(n==0)
return n;
vector<int> lps(n,0);
for(int i=1,j=0;i<n;)
{
if(needle[i]==needle[j])
lps[i++]=++j;
else if(j==0)
i++;
else
j=lps[j-1];
}
for(int i=0,j=0;i<m;)
{
if(haystack[i]==needle[j])
{
i++;
j++;
}
if(j==n)
{
return i-j;
}
else if(i<m && haystack[i]!=needle[j])
{
if(j==0)
{
i++;
}
else
{
j = lps[j-1];
}
}
}
return -1;
}
};
```
#### python version
```python
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
h,n = len(haystack),len(needle)
if(n==0):
return 0
if(h<n):
return -1
i,j, lps = 1,0, [0]*n
while(i<n):
if(needle[i]==needle[j]):
j += 1
lps[i] = j
i += 1
elif(j==0):
i+=1
else:
j = lps[j-1]
i,j = 0,0
while(i<h):
if(haystack[i]==needle[j]):
i+=1
j+=1
if(j==n):
return i-j
elif(i<h and haystack[i]!=needle[j]):
if(j==0):
i+=1
else:
j = lps[j-1]
return -1
```
### 459. Repeated Substring Pattern
#### c++ version
```cpp
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
vector<int> lps(n,0);
for(int i=1,j=0;i<n;)
{
if(s[i]==s[j])
lps[i++]=++j;
else if(j==0)
i++;
else
j=lps[j-1];
}
return lps[n-1]&&(lps[n-1]%(n-lps[n-1])==0);
}
};
```
#### python version
```python=
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
i,j,lps =1,0, [0]*n
while(i<n):
if(s[i]==s[j]):
j += 1
lps[i] = j
i += 1
elif(j==0):
i += 1
else:
j = lps[j-1]
return ((lps[n-1]>0) and (lps[n-1]%(n-lps[n-1])==0))
```
### 686. Repeated String Match
#### c++ version
```cpp
class Solution {
public:
int repeatedStringMatch(string a, string b) {
int anum = a.size();
int bnum = b.size();
vector<int> lps(bnum,0);
for(int i=1,j=0;i<bnum;)
{
if(b[i]==b[j])
lps[i++] = ++j;
else if(j==0)
i++;
else
j = lps[j-1];
}
for(int i=0,j=0;i<anum;)
{
if(b[j]==a[(i+j)%anum])
{
j++;
}
if(j==bnum)
{
if((i+j)%anum==0)
return (i+j)/anum;
return (i+j)/anum+1;
}
else if(i<anum && b[j]!=a[(i+j)%anum])
{
if(j==0)
{
i++;
}
else
{
i += (j-lps[j-1]);
j = lps[j-1];
}
}
}
return -1;
}
};
```
#### python version
```python
class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
m,n = len(a),len(b)
i,j,lps = 1,0,[0]*n
while(i<n):
if(b[i]==b[j]):
j += 1
lps[i] = j
i += 1
elif(j==0):
i += 1
else:
j = lps[j-1]
i,j = 0,0
while(i<m):
if(b[j]==a[(i+j)%m]):
j+=1
if(j==n):
if((i+j)%m==0):
return (i+j)//m
return ((i+j)//m)+1
elif(i<m and b[j]!=a[(i+j)%m]):
if(j==0):
i+=1
else:
i+=(j-lps[j-1])
j = lps[j-1]
return -1
```
Sign in with Wallet
Connect another wallet