47 lines
1023 B
Python
47 lines
1023 B
Python
import manacher
|
|
|
|
|
|
def test_empty():
|
|
assert manacher.longest_palindrome("") == ""
|
|
|
|
|
|
def test_single():
|
|
assert manacher.longest_palindrome("a") == "a"
|
|
|
|
|
|
def test_known():
|
|
cases = {
|
|
"babad": "bab",
|
|
"cbbd": "bb",
|
|
"a": "a",
|
|
"ac": "a",
|
|
"racecar": "racecar",
|
|
"abacdfgdcaba": "aba",
|
|
"aaaa": "aaaa",
|
|
"abacaba": "abacaba",
|
|
}
|
|
for s, exp in cases.items():
|
|
got = manacher.longest_palindrome(s)
|
|
# accept any maximal-length palindrome
|
|
assert len(got) == len(exp), (s, got, exp)
|
|
assert got == got[::-1]
|
|
|
|
|
|
def test_all_same():
|
|
s = "x" * 1000
|
|
assert manacher.longest_palindrome(s) == s
|
|
|
|
|
|
def test_no_palindrome_longer_than_one():
|
|
s = "abcdef"
|
|
assert len(manacher.longest_palindrome(s)) == 1
|
|
|
|
|
|
def test_even_center():
|
|
assert manacher.longest_palindrome("abba") == "abba"
|
|
|
|
|
|
def test_distinct_substrings_smoke():
|
|
out = manacher.all_palindromic_substrings("aaa")
|
|
assert set(out) == {"a", "aa", "aaa"}
|