Testing example

stuff.py

# kmp.py
def get_prefix(string):
    l = len(string)
    ret = [0] * l
    border = 0
    for i in xrange(1, l):
        while border > 0 and string[i] != string[border]:
            border = ret[border - 1]
        if string[i] == string[border]:
            border += 1
        else:
            border = 0
        ret[i] = border
    return ret


def kmp(string, pattern):
    prefix = get_prefix(pattern + "$" + string)
    lp, ls = len(pattern), len(string)
    ret = []
    for i in xrange(lp, lp + ls + 1):
        if prefix[i] == lp:
            ret.append(i - 2 * lp)
    return ret

# conftest.py
import pytest
from random import randint as ri


def random_string(length):
    return "".join(chr(ri(97, 122)) for _ in xrange(length))



@pytest.fixture
def rs(request):
    args = request.node.funcargs
    n = args["n"]
    k = args["k"]
    return (
        random_string(n),
        random_string(k))


# test_kmp.py
from kmp import kmp
import pytest
from random import randint as ri

TOTAL = 1000
MLEN = 40


def brute_check(string, substring):
    ls, lsu = len(string), len(substring)
    ret = []
    for i in xrange(ls + 1 - lsu):
        if string[i:(i + lsu)] == substring:
            ret.append(i)
    return ret


@pytest.mark.parametrize(
    "n, k", 
    [(el, ri(1, el)) for el in (ri(1, MLEN) for _ in xrange(TOTAL))])
def test_kmp(n, k, rs):
    string, substring = rs
    assert kmp(string, substring) == brute_check(string, substring)