题目标题

AB两个字符串,求A的连续子串中,在B中出现的最长的那个(最长公共子串问题)

难度:初级

数据分析
参考解析

coding:utf-8

‘’’
求两个字符串的最长公共子串
思想:建立一个二维数组,保存连续位相同与否的状态
‘’’
def getNumofCommonSubstr(str1, str2):
lstr1 = len(str1)
lstr2 = len(str2)
record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)] # 多一位
maxNum = 0 # 最长匹配长度
p = 0 # 匹配的起始位

  1. for i in range(lstr1):
  2. for j in range(lstr2):
  3. if str1[i] == str2[j]:
  4. # 相同则累加
  5. record[i+1][j+1] = record[i][j] + 1
  6. if record[i+1][j+1] > maxNum:
  7. # 获取最大匹配长度
  8. maxNum = record[i+1][j+1]
  9. # 记录最大匹配长度的终止位置
  10. p = i + 1
  11. return str1[p-maxNum:p], maxNum

if name == ‘main‘:
str1 = raw_input()
str2 = raw_input()
res = getNumofCommonSubstr(str1, str2)
print(res)