[python] kmp算法实现和测试

kmp算法实现

class kmp():
    def __init__(self, mStr, subStr):
        self.mStr = mStr
        self.subStr = subStr
    
    def get_next(self, loc) -> int:
        k = 0
        while k < loc and self.subStr[0:k + 1] == self.subStr[loc-k-1:loc]:
            k += 1
        return k
    
    def isin_mStr(self) -> bool:
        lens = len(self.mStr)
        slens = len(self.subStr)
        i = j = 0
        while i < lens:
            while j < slens and i < lens and self.subStr[j] == self.mStr[i]:
                j += 1
                i += 1
            if j == slens:
                return True
            elif j == 0:
                i += 1
            else:
                j = self.get_next(j)
        return False

测试

from kmp import kmp
import pytest

testlist = [
    ("abc","ab",True),
    ("a","b", False),
    ("abcdabcdef","abcdefg",False)
]
@pytest.mark.parametrize("nstr, substr, result", testlist)
def test_kmp(nstr, substr,result):
    assert kmp(nstr,substr).isin_mStr() == result

collected 3 items

test_kmp.py ...                                                                               [100%] 

== 3 passed in 0.04s ==