描述

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

数据范围：字符串长度1\le length \le300 \1≤length≤300 
进阶：时间复杂度：O(n^3)\O(n3) ，空间复杂度：O(n)\O(n) 

输入描述：

输入两个字符串

输出描述：

返回重复出现的字符

示例1

输入： 
abcdefghijklmnop
abcsafjklmnopqrstuvw
复制
输出： 
jklmnop
思路：在短字符串中从后往前找子串，然后判断其是否在b中，并且使用max1来记录最长子串的长度，如果扫描到前面发现有同样长甚至更长的子串，那么就更新子串，最后留下来的子串就是在a中最先出现的最长子串了
代码： 
a=input()
b=input()
#保证a比b短
if len(a)>len(b):
    c=a
    a=b
    b=c
max1=0
#注意这里使用reversed把i的变化范围改为从大到小是方便从a的末尾开始扫描
#这样才能实现同样长度的子串，后扫描到的会覆盖前面扫描的，由于从尾部开始扫描
#正好就是在a中最先出现的最长子串最后留下来了，也可以使用下面注释那一行改变i的值
for i in reversed(range(len(a))):
##    i=len(a)-i-1
    for j in range(i+1,len(a)+1):
        if a[i:j] in b and len(a[i:j])>=max1:
            max1=len(a[i:j])
            d=a[i:j]
print(d)