专栏首页算法与编程之美答粉丝问|求给定字符串中最长公共子串

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

问题描述

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

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

解决方案

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

如何选最短的字符串小编就不多说了,我们直接来看如何切片。前面已经说了,要从最长子串也就是本身开始依次递减一个字符进行比对。这里我们用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) #将输入的每行字符串加入列表lisss1 = lis[0]for a in lis: if len(a)<len(ss1): ss1 = a #用for循环找出列表lis中最短字符串,并求其长度,然后从列表lis中删除l = len(ss1)lis.remove(ss1)num2 = 0 #定义一个计数变量for n in range(l): #以最短字符串长度来定循环次数,遍历每一种子字符串长度的情况 for b in range(n+1): #遍历一种长度的每一种子字符串 num1 = 0 for m in lis: #遍历lis中的每一个字符串 if ss1[b:l-n+b] in m and ss1[b:l-n+b] not in lis1: #用切片依次切出一种长度的每种子字符串 num1 += 1 #若该子字符串在字符串m中,并且不与前面切出过的子字符串相同计数器就加1 if num1 == N-1: #如果计数器的值与lis的长度及N-1相等,说明该子字符串在lis的每一个字符串中 num2 = 1 #找到一个最长公共子字符串计数器num2就等于1 lis1.append(ss1[b:l-n+b]) #满足的条件的子字符串加到列表lis1中 print(ss1[b:l-n+b],end=' ') #输出所有相同长度且都为最长公共子字符串的子字符串 if num2 == 1: break #如果循环完一种长度的所有种子字符串且找到了最长公共子字符串,循环终止

结语

小编刚拿到这个问题的时候,以为很简单,随便做了一下,在检测时才发现漏洞百出,最后也是在纸上分析了切片的规律,找出了其中的逻辑关系,才得以解决这个问题,所以小编想告诉大家,遇到问题还是先分析分析,最好是在纸上画一画。

END

实习编辑 | 王文星

责 编 | 江来洪

本文分享自微信公众号 - 算法与编程之美(algo_coding),作者:江来洪

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python|字符串的知识

    字符串是字符的序列表示,可以由一对单引号(‘),双引号(“)或三引号(‘’’)构成。其中单引号和双引号都可以表示单行字符,两者作用相同。使用单引号时,双引号可以...

    算法与编程之美
  • Python|字符串相关问题

    在python中经常遇到一些关于求字符串的问题,比如;找出最长回文字符串,找出字符串中不含重复字符的最长字符串,这时我们总是被这些问题给难住,该如何解决呢?

    算法与编程之美
  • Java|Lexer分析报告

    rules是一个数组,数组里面是单个对象,然后利用utils的some方法将rules数组里的每一项的regex放进去判断是否满足条件。

    算法与编程之美
  • 【每日必python】第一期:python字符串操作函数总结

    周旋
  • leecode刷题(15)-- 验证回文字符串

    刚开始和上一题一样,我也没理解“回文字符串”是什么意思,后来想了下,“回文字符串”其实就是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就...

    希希里之海
  • 请解释一下String为什么不可变?

    不可变对象是指一个对象的状态在对象被创建之后就不再变化。不可改变的意思就是说:不能改变对象内的成员变量,包括基本数据类型的值不能改变,引用类型的变量不能指向其他...

    剑走天涯
  • 零基础学Python--------第5章

     在Python开发过程中,为了实现某项功能,经常需要对某些字符串进行特殊处理,如拼接字符串、截取字符串、格式化字符串等。下面将对Python中常用的字符串操作...

    py3study
  • python测试开发之路第三讲-字符串

    这两天魔都阴雨绵绵,气温也下降了很多,小伙伴们在努力工作的同时,别忘了保暖,此时,鲲鹏老师正在魔都的一角给大家撸着笔记,希望能够一起学习进步,关于前两篇文章的排...

    cctester
  • PHP字符串操作函数

    这两个函数都是按字节进行字符串比较,其中strcmp()函数区分大小写,strcasecmp()不区分大小写

    白胡杨同学
  • Python字符串的基本用法总结

        字符串序列用于表示和存储文本,python中字符串是不可变对象。通常由单引号(' ),双引号(" ),三引号(''' """)包围,其中三引号可以由多行...

    py3study

扫码关注云+社区

领取腾讯云代金券