设有两个字符串abaabba和bbbabaa，问它们的最长子串是什么？这个问题的一个应用就是比较两个病毒的基因，从而给出两者的相似度。这里我们用递归方法解决这个难题。
输入参数显然是两个字符串s1和s2。递归边界是s1和s2中至少有一个是空字符串[1]，此时它们的最大子串就是空字符串。递归假设是只要s1或s2中少了一个字符，则程序总能计算出它们剩余部分的最长子串。
递归推导时可以把s1的第一个字符c拎出来单独考虑。如果最长子串中不含有c，则可以递归地求s1的剩余部分与s2的最长子串r1。否则可以针对s2中出现的每一个c，求其后的字符串与s1的剩余部分的最长头子串[2]，设为r2。最后比较len(r1)和len(r2)+1，保留大的那个即可。代码如下：
最长子串问题
def longest_substring(s1, s2, f1=0, f2=0):
# 为了避免代价高的字符串复制操作，使用f1和f2指明字符串起始位置
if f1 >= len(s1) or f2 >= len(s2):
return ''
c = s1[f1]
r1 = longest_substring(s1, s2, f1+1, f2)
start = f2
while True:
pos = s2.find(c, start) # 从start处开始找字符c
if pos < 0:
break
r2 = longest_head(s1, s2, f1+1, pos+1)
if len(r2) + 1 > len(r1): # 保留最长的子串
r1 = c + r2
start += len(r2) + 1
return r1
def longest_head(s1, s2, f1, f2):
# 获取s1和s2分别从f1和f2开始的最长头子串
f1_start = f1
while f1 < len(s1) and f2 < len(s2) and s1[f1] == s2[f2]:
f1 += 1
f2 += 1
return s1[f1_start: f1]
if __name__ == '__main__':
print(longest_substring('abaabba', 'bbbabaa'))
程序运行的结果是：abaa。
[1] 即不含有任何字符的字符串，比如''。空字符串的长度为0。
