50 lines
1.3 KiB
Python
50 lines
1.3 KiB
Python
import os, sys, unittest
|
|
sys.path.insert(0, os.path.dirname(__file__))
|
|
from lcp_array import build_suffix_array, build_lcp, lcp_of
|
|
|
|
|
|
class TestLCP(unittest.TestCase):
|
|
def _check(self, text):
|
|
sa = build_suffix_array(text)
|
|
lcp = build_lcp(text, sa)
|
|
if not text:
|
|
self.assertEqual(lcp, [])
|
|
return
|
|
self.assertEqual(lcp[0], 0)
|
|
for i in range(1, len(text)):
|
|
a, b = sa[i-1], sa[i]
|
|
self.assertEqual(lcp[i], lcp_of(text, a, b),
|
|
"mismatch at %d for %r" % (i, text))
|
|
|
|
def test_banana(self):
|
|
self._check("banana")
|
|
|
|
def test_empty(self):
|
|
self.assertEqual(build_lcp("", []), [])
|
|
|
|
def test_single(self):
|
|
self._check("a")
|
|
|
|
def test_repeated(self):
|
|
self._check("aaaa")
|
|
|
|
def test_random(self):
|
|
import random
|
|
for _ in range(200):
|
|
n = random.randint(0, 12)
|
|
alphabet = "ab"
|
|
t = "".join(random.choice(alphabet) for _ in range(n))
|
|
self._check(t)
|
|
|
|
def test_invalid_sa_length(self):
|
|
with self.assertRaises(ValueError):
|
|
build_lcp("abc", [0, 1])
|
|
|
|
def test_invalid_sa_permutation(self):
|
|
with self.assertRaises(ValueError):
|
|
build_lcp("abc", [0, 0, 2])
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main()
|