KMP Frequency of a Sub string in a string

 Given an input string and a substring. Find the frequency of occurrences of a substring in a given string.

Input : man (pattern)
        dhimanman (string)
Output : 2

Solution:

def lpsarray(pat,m,lps):
    l=0
    i=1
    lps[0]=0
    while(i<m):
        if pat[i]==pat[l]:
            l+=1
            lps[i]=l
            i+=1
        else:
            if l!=0:
                l=lps[l-1]
            else:
                lps[i]=0
                i+=1
def kmpsearch(pat,txt):
    m=len(pat)
    n=len(txt)
    lps=[None]*m
    lpsarray(pat,m,lps)
    i=0
    j=0
    res=0
    next_i=0
    while(i<n):
        if pat[j]==txt[i]:
            j=j+1
            i+=1
        if j==m:
            j=lps[j-1]
            res+=1
            if lps[j]!=0:
                next_i+=1
                i=next_i
                j=0
        elif i<n and pat[j]!=txt[i]:
            if(j!=0):
                j=lps[j-1]
            else:
                i+=1
        
    return res 
        
txt="aaababbbaaa"
pat="ab"

ans=kmpsearch(pat,txt)
print(ans)

        
        
        
 Solution Credit:frequency-substring-string