答粉丝问|求给定字符串中最长公共子串

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

前几日有粉丝问了这样一个问题：

经过小编思考过后，特意写了此文来为该粉丝解答疑惑。

解决方案

首先抓取问题的关键点，一是“最长”，二是“公共”。然后再看问题都是在字符串中操作，所以小编首先想到的就是对字符串进行一系列切片操作。具体怎么实施，还得回到问题要求来。首先处理“最长问题”，既然是找最长，我们不妨就从最长子串开始依次递减一个字符进行比对。再结合“公共”来看，可知公共子串必定由给定字符串集中最短字符串决定，所以小编想到了先选取出给定字符串集中最短的字符串进行切片操作。

如何选最短的字符串小编就不多说了，我们直接来看如何切片。前面已经说了，要从最长子串也就是本身开始依次递减一个字符进行比对。这里我们用abcde来举例，第一个子串肯定是abcde，然后判断其他几个字符串中是否都含有abcde这个子串，如果是就输出，这自然就是最长的公共子串了，如果不是，那就进入下一个循环。第二个子串也就是四个字符的abcd，比对方法同上，同样四个字符的还有bcde，再三个字符的，abc,bcd,cde,两个字符的,ab,bc,cd,de,一个字符的，a,b,c,d,e。具体过程就是这样。

那这个过程有什么规律呢？这自然是有的，小编发现每一个长度的字符串个数n与原字符串长度L和子串长度l有n=L-l+1的关系，找出这个关系后就可以对循环定次数了，同样切片的下标自然也是可以运用这个关系的。

分析完问题后，整理下思路，将其转化为程序语言。

代码示例：

N = int(input())            #输入一个整数，代表你下面要输的行数

lis = []

lis1 = []                   #定义两个空列表备用

for i in range(N):

    ss = input()           #输入需要比较的字符串

    lis.append(ss)          #将输入的每行字符串加入列表lis

ss1 = lis[0]

for a in lis:

    if len(a)