54 lines
1.7 KiB
Python
54 lines
1.7 KiB
Python
import unittest
|
|
from kmp import build_pi, search, search_count
|
|
|
|
|
|
class TestKMP(unittest.TestCase):
|
|
def test_pi(self):
|
|
self.assertEqual(build_pi("aabaaab"), [0,1,0,1,2,2,3])
|
|
self.assertEqual(build_pi("aaaa"), [0,1,2,3])
|
|
self.assertEqual(build_pi(""), [])
|
|
self.assertEqual(build_pi("abc"), [0,0,0])
|
|
|
|
def test_search_basic(self):
|
|
self.assertEqual(search("ababcababa", "aba"), [0,5,7])
|
|
self.assertEqual(search("aaaa", "aa"), [0,1,2])
|
|
self.assertEqual(search("hello world", "xyz"), [])
|
|
self.assertEqual(search("abc", "abcd"), [])
|
|
|
|
def test_overlapping(self):
|
|
self.assertEqual(search("aaaaa", "aaa"), [0,1,2])
|
|
|
|
def test_single(self):
|
|
self.assertEqual(search("abc", "a"), [0])
|
|
self.assertEqual(search("abc", "c"), [2])
|
|
|
|
def test_empty_pattern(self):
|
|
self.assertEqual(search("abc", ""), [])
|
|
self.assertEqual(search("", ""), [])
|
|
|
|
def test_full_text(self):
|
|
self.assertEqual(search("abc", "abc"), [0])
|
|
|
|
def test_count(self):
|
|
self.assertEqual(search_count("ababab", "ab"), 3)
|
|
self.assertEqual(search_count("aaaa", "aa"), 3)
|
|
|
|
def test_unicode(self):
|
|
self.assertEqual(search("cafécafé", "café"), [0,4])
|
|
|
|
def test_random_vs_naive(self):
|
|
import random
|
|
rng = random.Random(42)
|
|
alpha = "ab"
|
|
for _ in range(200):
|
|
n = rng.randint(0, 60)
|
|
m = rng.randint(1, 8)
|
|
text = "".join(rng.choice(alpha) for _ in range(n))
|
|
pat = "".join(rng.choice(alpha) for _ in range(m))
|
|
naive = [i for i in range(len(text)-m+1) if text[i:i+m] == pat]
|
|
self.assertEqual(search(text, pat), naive)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main()
|