擅长:python、mysql、java
<p>仅仅举一个小例子还不够好。这是农历年中最不明确的问题。但是,假设重叠只能出现在结尾处,并且每个单词只测试两次(针对当前输出的每一端),并且您想要最大的重叠,则这将完成以下工作:</p>
<p><em>[修复错误后编辑]</em></p>
<pre><code>def glue(a, b):
maxn = 0
for n in xrange(1, 1 + min(len(a), len(b))):
suffix = a[-n:]
prefix = b[:n]
if prefix == suffix:
maxn = n
# BUG: return maxn, a[:-maxn] + b
# FAILS when maxn == 0
# EXTRA TEST: ['nil', 'overlap']
return a + b[maxn:]
def multiglue(words):
if not words: return ""
result = words[0]
for word in words[1:]:
nx, rx = glue(result, word)
ny, ry = glue(word, result)
result = rx if nx > ny else ry
return result
tests = [line.split() for line in """
one
two one
one two
overlap nil
nil overlap
toad dog rabbit
frog ogham
ogham frog
hopper grasshopper
grass grasshopper person
foooo oooof
oooof foooo""".splitlines()]
for test in tests:
out = multiglue(test)
print test, repr(out)
</code></pre>
<p>输出:</p>
^{pr2}$