120 lines
2.5 KiB
Python
120 lines
2.5 KiB
Python
'''Longest common substring'''
|
|
|
|
from itertools import accumulate, chain
|
|
from functools import reduce
|
|
|
|
|
|
# longestCommon :: String -> String -> String
|
|
def longestCommon(s1):
|
|
'''The longest common substring of
|
|
two given strings.
|
|
'''
|
|
def go(s2):
|
|
return max(intersect(
|
|
*map(lambda s: map(
|
|
concat,
|
|
concatMap(tails)(
|
|
compose(tail, list, inits)(s)
|
|
)
|
|
), [s1, s2])
|
|
), key=len)
|
|
return go
|
|
|
|
|
|
# ------------------------- TEST -------------------------
|
|
def main():
|
|
'''Test'''
|
|
print(
|
|
longestCommon(
|
|
"testing123testing"
|
|
)(
|
|
"thisisatest"
|
|
)
|
|
)
|
|
|
|
|
|
# ----------------------- GENERIC ------------------------
|
|
|
|
# compose :: ((a -> a), ...) -> (a -> a)
|
|
def compose(*fs):
|
|
'''Composition, from right to left,
|
|
of a series of functions.
|
|
'''
|
|
def go(f, g):
|
|
def fg(x):
|
|
return f(g(x))
|
|
return fg
|
|
return reduce(go, fs, lambda x: x)
|
|
|
|
|
|
# concat :: [String] -> String
|
|
def concat(xs):
|
|
'''The concatenation of all the elements
|
|
in a list or iterable.
|
|
'''
|
|
return ''.join(xs)
|
|
|
|
|
|
# concatMap :: (a -> [b]) -> [a] -> [b]
|
|
def concatMap(f):
|
|
'''A concatenated list over which a function has been
|
|
mapped.
|
|
The list monad can be derived by using a function f
|
|
which wraps its output in a list, (using an empty
|
|
list to represent computational failure).
|
|
'''
|
|
def go(xs):
|
|
return chain.from_iterable(map(f, xs))
|
|
return go
|
|
|
|
|
|
# inits :: [a] -> [[a]]
|
|
def inits(xs):
|
|
'''all initial segments of xs, shortest first.'''
|
|
return accumulate(chain([[]], xs), lambda a, x: a + [x])
|
|
|
|
|
|
# intersect :: [a] -> [a] -> [a]
|
|
def intersect(xs, ys):
|
|
'''The ordered intersection of xs and ys.
|
|
intersect([1,2,2,3,4])([6,4,4,2]) -> [2,2,4]
|
|
'''
|
|
s = set(ys)
|
|
return (x for x in xs if x in s)
|
|
|
|
|
|
# scanl :: (b -> a -> b) -> b -> [a] -> [b]
|
|
def scanl(f):
|
|
'''scanl is like reduce, but defines a succession of
|
|
intermediate values, building from the left.
|
|
'''
|
|
def go(a):
|
|
def g(xs):
|
|
return accumulate(chain([a], xs), f)
|
|
return g
|
|
return go
|
|
|
|
|
|
# tail :: [a] -> [a]
|
|
# tail :: Gen [a] -> [a]
|
|
def tail(xs):
|
|
'''The elements following the head of a
|
|
(non-empty) list.
|
|
'''
|
|
return xs[1:]
|
|
|
|
|
|
# tails :: [a] -> [[a]]
|
|
def tails(xs):
|
|
'''All final segments of xs,
|
|
longest first.
|
|
'''
|
|
return [
|
|
xs[i:] for i in
|
|
range(0, 1 + len(xs))
|
|
]
|
|
|
|
|
|
# MAIN ---
|
|
main()
|