python实现公共子串

㈠ 459. 重复子字符串（python）

难度：★☆☆☆☆
类型：数组

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

示例 2:
输入: "aba"
输出: False

示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

这里我们观察到一个现象，对于一个字符串s，我们将两个该字符串连接成一个更长的字符串（s_double），该字符串中至少包含两个s子串，如果s可以由多个重复单元构成，那么合并后的字符串中一定包含超过两个s子串（可重叠），例如，两个"abab"组成的"abababab"中包含3个"abab"，而两个"aba"组成的"abaaba"则只包含两个"aba"，根据这个原理，我们只需要统计s+s中s（可重叠）出现的次数，并与2比较即可。

这里为了简化计算，我们把s+s的首尾两端字符去掉，这样就只需要查看s是否在剩余的字符串中即可。编码时通过索引范围[1:len(s)*2-1]起到去掉首尾两端字符的效果。

如有疑问或建议，欢迎评论区留言~

㈡ Python字符串split及rsplit方法原理详解

1.描述

split()方法通过指定分隔符对字符串进行切片，如果参数num有指定值，则分隔num+1个子字符串，默认分隔符为所有空字符，包括空格、换行(\n)、制表符(\t)等

rstrip()方法通过

2.语法

str.split([sep=None][,count=S.count(sep)])

str.rsplit([sep=None][,count=S.count(sep)])

3.参数

sep -- 可选参数，指定的分隔符，默认为所有的空字符，包括空格、换行(\n)、制表符(\t)等

count -- 可选参数，分割次数，默认为分隔符在字符串中出现的总次数

4.返回值

返回分割后的字符串行表，可以用新字符串来接收

5.实例

str1 = "Hao123 hao456 hAo789"

new_str = str1.split()

new_str2 = str1.split(' ', 1)

new_str3 = str1.rsplit(' ', 1)

print(new_str)

print(new_str2)

print(new_str3)

#输出结果如下：

['Hao123', 'hao456', 'hAo789']

['Hao123', 'hao456 hAo789']

['Hao123 hao456', 'hAo789']

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

㈢ Python 标准库模块 - re

正则表达式引擎对正则表达式文本进行编译生成正则表达式对象，再由正则表达式对象对目标文本进行匹配，后返回匹配结果。

正则表达式中一共包含 2 中字符： 普通字符 、 元字符

匹配单个字符的元字符及其含义：

匹配重复性的元字符及其含义：

匹配位置的元字符及其含义：

分组匹配的元字符及其含义：

表示或运算的元字符：

转义元字符：

在 Python 中使用正则表达式，我们需要借助 re 模块提供的强大 API，下面我们就来学习几个 re 模块常用的接口吧~

参数说明： findall("正则表达式", "要匹配的字符串", flags=标志1|标志2|...)
返回值：以列表形式返回匹配到的字符串。

下面，我们用 findall 返回 Python 之禅中首尾用到的反义词：

运行结果：

当正则表达式中含有一个以上分组时， findall 返回的列表由元组构成，元组中包含每个分组匹配到的内容。如果只有一个分组，则返回由该分组匹配到的内容组所构成的列表：

match 函数返回的结果是一个 SRE_Match 对象：

SRE_Match 具有很多的属性，比如 .string 属性可以方便我们我获取在匹配时输入的字符串：

属性 .re 可以获取匹配时使用的编译后的正则表达式模式：

由于默认使用了 re.UNICODE ，所以我们这里的 w 可以匹配中文字符。

属性 .regs 则以列表的形式返回正则表达式匹配到的内容以及各个分组陪陪到的内容，不过请注意，返回的都是索引的形式：

可以使用序列切片来看一下我们的正则表达式及其中的两个分组所匹配到的内容：

SRE_Match 对象也提供了非常多好用的方法，比如 groups 可以获取各个分组匹配到的内容：

group 则可以灵活地获取正则表达式或对应分组匹配到的内容：

如果使用的正则表达式定义了分组的名称， group 还可以通过名称获取相应分组匹配的内容：

在定义了分组的名称之后，还可以方便地使用 groupdict 以字典的形式返回所有分组匹配的结果：

最后需要注意的是， match 从字符串的开头开始匹配，如果开头不符合要求，则直接返回 None 。

与 match 匹配开头不同， search 匹配第一个符合规则的字符串，未成功则返回 None 。参数： re.search(pattern, string, flags=0) ；返回值同 match 。

在介绍 match 的使用时，最后一个例子，由于我们在字符串前面添加了 'PYTHON' 导致 match 使用原来的正则表达式无法匹配，返回 None 。此时，使用 search 就可以迎刃而解啦：

运行结果：

小结：

参数： re.split(pattern, string, maxsplit=0, flags=0) ， split 功能非常强大，以正则表达式匹配到的标志来分隔字符串，比如下面这样一个混乱的字符串，我们要提取其中所有的数字：

下面，我们就来详细介绍一下 split 的用法。

首先，是以单字符切割：

以分号切割时，共产生了 4 个子字符串，放在列表中返回。
下面，还是以单字符切割，但可以使用正则表达式中的 [] 来指定多种字符：

由于字符串 line 中有连续的 2 个分号，逗号或者空格，因此可以使用 [;s,]+ 来切割：

最后，上面的字符串在切割时，分隔符都没有被保留下来，使用括号捕获分组，即可保留分隔符：

re.sub 提供比字符串的 replace 方法更加强大的功能：对于输入的字符串 string ,利用正则表达式 pattern 强大的字符串处理功能，实现复杂的字符串替换处理为 repl ，返回被替换后的字符串。

下面的例子中，我们将句子中多余的空格和数字去掉：

如果想要知道替换过程中，共发生了多少次替换，可以使用 subn ：

小结：

上述的案例中，我们每次都需要传入正则表达式，相应的函数每次在调用时，都需要编译一次正则表达式。如果上述过程需要多次重复，那么每次都去耗费时间编译正则表达式是很不划算的。

re 模块为我们提供了 compile 函数，用来编译正则表达式模式，返回编译好模式。因此，可以把那些常用的正则表达式编译成正则表达式对象，以提高效率。

格式： re.compile(pattern, flags=0) ，其中 pattern 为编译时用的表达式字符串， flags 为编译标志位，用于修改正则表达式的匹配方式，如：是否区分大小写，多行匹配等。常用的 flags 有：

注：使用按位或 | 连接多个 flags 。

我们上述介绍的 re 模块的匹配、分割、替换函数， compile 函数的返回值类提供了相应的方法，使用方式类似，只是不需要传入正则表达式字符串而已。

由于用法几乎一致，这里就不一一举例啦~

贪婪模式 ： * + ? {m,n} ，正则表达式的重复默认总是尽可能多得向后匹配内容。

非贪婪模式 ： *? +? ?? {m,n}? ，尽可能少的匹配内容。

㈣ Python字符串是什么，如何使用

字符串的表示

字符串可以被成对的单引号(single quote)或双引号(double quotes)包围起来，这两者的作用是一样的：

更多关于Python的基础性知识可以看下这个网页的视频教程，Python常见的数据类型及使用方法掌握，希望我的回答能帮到你。

㈤ 【python】求两个字符串的公共字串

题目：找出两个字符串的最长公共字串，例如字符串“abccade”与字符串“dgcadde”的最长公共子串为“cad”。

分析：动态规划法。通过把中间的比较结果记录下来，从而可以避免字符的重复比较。：

首先定义二元函数（i，j）：表示分别以s1[i],s2[j]结尾的公共子串的长度，显然，f（0， j） = 0 (j >= 0),f(i, 0) = 0(i >= 0),那么对于f(i +1, j + 1)而言，则有如下两种取值：
（1) f(i + 1, j +1) = 0,当str1[i + 1] != str2[j + 1]时

（2）f(i + 1, j +1) = f(i, j) + 1,当str1[i + 1] == str2[j + 1]时

根据这个公式可以计算出f(i, j)（0<= i<=len(s1), 0 <= j <= len(s2)，所有的值，从而可以找出最长的子串。

def getMaxSubStr(str1, str2):

    len1 = len(str1)

    len2 = len(str2)

    sb = ''

    maxs = 0  # 用来记录最长公共子串的长度

    maxI = 0  # 用来记录最长公共字串最后一个字符的位置

    # 申请新的空间来记录公共字串长度信息

    M = [([None] * (len1 + 1)) for i in range(len2 + 1)]

    i = 0

    while i < len1 + 1:

        M[i][0] = 0

        i += 1

    j = 0

    while j < len2 + 1:

        M[0][j] = 0

        j += 1

    # 通过利用递归公式填写新建得二维数组（公共字串得长度信息）

    i = 1

    while i < len1 + 1:

        j = 1

        while j < len2 + 1:

            if list(str1)[i - 1] == list(str2)[j - 1]:

                M[i][j] = M[i - 1][j - 1] + 1

                if M[i][j] > maxs:

                    maxs = M[i][j]

                    maxI = i

            else:

                M[i][j] = 0

            j += 1

        i += 1

    i = maxI - maxs

    while i < maxI:

        sb = sb + list(str1)[i]

        i += 1

    return sb

if __name__ == "__main__":

    str1 = 'abccade'

    str2 = 'dgcadde'

    print(getMaxSubStr(str1, str2))

程序运行结果：

cad

㈥ python判断字符串（string）是否包含（contains）子字符串的方法的代码

下边内容是关于python判断字符串（string）是否包含（contains）子字符串的方法的内容。

方法2：使用find函数实现contains的功能

s = "This be a string"

if s.find("is") == -1:

    print "No 'is' here!"

else:

    print "Found 'is' in the string."

㈦ Python包之OS

参考： https://docs.python.org/3/library/os.html

Python中对OS模块的定位是：提供了使用操作系统的工具接口。
如果你想读写文件，可以参考open()；
如果你想操作文件路径，参考os.path模块；
如果你想在命令行读取所有文件的所有行，参考fileinput模块；
如果你想创建临时文件或目录，参考tempfile模块；
如果你想更高级的文件和路径处理，参考shutil模块；

内置的OSError异常类型，比如在使用os模块中的函数接口时，在参数中提供了无效的文件或路径，就回报错os.error。

该变量返回当前操作系统的类型，当前只注册了3个值：分别是posix , nt , java， 对应linux/windows/java虚拟机。

在Python中，文件名，命令行参数和环境变量都是用字符串类型来表示。

接下来的这些函数和数据提供了当前进程和用户的信息状态和操作接口。

返回进程控制终端的文件名，适用于Unix系统。

返回字符串到环境变量的映射。

改变当前工作目录到指定的路径，path为要切换到的新路径。

通过文件描述符改变当前工作目录。
文件描述符是内核为了高效管理已经被打开的文件所创建的索引，

进程通过文件描述符来访问文件。 在程序刚启动的时候默认有3个文件描述符：0(标准输入)，1(标准输出)，2(标准错误)，系统默认提供了 0～2的文件描述符，之后的 当我们进行 open,create等操作的时候 自动添加进表

所以int creat(const char * ,mode_t)返回的文件int 就是你所进行操作的文件的唯一身份标示，

然后你只要拿着这个ID 然后告诉系统给我找xx， write(int fd,char *buf,int lenght) 通过fd得到准确文件 然后写入。

当我们新建creat，打开open 之后，得到的fd 是从3开始的 因为前面的三个被系统占了在OS X系统下测试 文件描述符表 自增，当释放close之后，fd变成－1，如果再继续新建 则填补之前的空缺。

返回当前工作目录。

把字符串类型的文件名翻译成bytes类型的文件名；os.fsdecode()实现相反的功能。

返回路径的文件系统表示。

如果环境变量中存在key，返回环境变量key的值，否则返回default的值。

设置环境变量key的值为value。

使用当前uid/gid检测对路径path是否有访问权限。其中，path为要检测是否有权限的路径，mode为权限类别，值可以为os.F_OK、os.R_OK、os.W_OK、os.X_OK中的一个或多个；

切换当前的工作路径为path指定的路径。

设置路径path的标记为flags，flags为数字标记，多个flags可以使用or组合。flags可以为以下值或以下值的组合：

更改文件或目录的权限。
path -- 文件名路径或目录路径
mode -- 可用以下选项按位或操作生成， 目录的读权限表示可以获取目录里文件名列表， 写权限表示可以获取文件并且可以修改内容，执行权限表示可以把工作目录切换到此目录 ，删除添加目录里的文件必须同时有写和执行权限 ，文件权限以用户id->组id->其它顺序检验,最先匹配的允许或禁止权限被应用。

更改路径的拥有者和group id为uid和gid。如果不修改可以设置为-1，并且需要超级用户权限来执行权限修改操作。
path -- 设置权限的文件路径
uid -- 所属用户ID
gid -- 所属用户组ID

更改当前进程的根目录为path。

返回当前工作目录。

返回path目录路径下的文件列表，列表没有固定的顺序。

创建目录path。如果目录已经存在，会抛出异常FileExistsError。

递归的目录创建，递归的意思是创建所有到达叶子目录的中间目录。

从原始设备号（通常是stat中的st_dev或st_rdev）中提取设备major号码。

从原始设备号（通常是stat中的st_dev或st_rdev）中提取设备minor号码。

根据设备的major号码和minor号码组成原始设备号。

删除文件路径path。如果path指向的是目录路径，会抛出异常IsADirectoryError。如果要删除目录，使用rmdir。

递归的删除目录。与rmdir功能相似，不同的是，如果叶子目录被删除之后，removedirs会连续的删除每一层上级目录，直到抛出异常（异常会被忽略，因为异常通常意味着上层目录为非空目录）。

重命名文件或路径src为dst，如果dst已经存在，会抛出异常。

递归的重命名文件或目录。功能与rename类似，不同在于，renames首先创建new路径（即重命名之后的路径）的中间路径，然后创建完整new路径，最后，会使用removedirs删除掉old路径（实际上删除的是old路径与new路径不重合的部分）。

重命名文件或路径src为dst。如果dst是目录，抛出异常OSError。如果dst是文件且已经存在，且用户具有权限，dst会被替换掉。

删除path目录。如果path不存在，或者path非空，会抛出异常FileNotFoundError或OSError。如果要删除整个目录树，可以使用shutil.rmtree()。

返回path的绝对路径，效果等同于使用normpath：normpath(join(os.getcwd(), path))。

返回路径path的文件名，也就是对path调用os.path.split函数返回的元组的第二个元素。

paths为一个序列类型，其中每个元素表示一个路径，函数返回结果为每个元素所表示的路径的最长公共子路径。如果paths为空，或者paths同时包含绝对路径和相对路径，或者paths同时包含不同驱动类型的路径（比如Linux系统的路径和Windows系统的路径），则抛出异常ValueError。

list中的每个元素表示一个路径，函数返回每个路径的最长的共有路径前缀，因为计算方式为逐个字符进行比较，所以可能返回的结果并非有效的路径，如果要返回有效路径，可以使用commonpath。

返回path路径的目录部分，也就是对path调用os.path.split函数返回的元组的第一个元素。

如果path指向的路径已存在，则返回True，否则返回False。

在Unix和Windows系统中，返回path路径中的~被替换成用户的home目录之后的结果。

path路径中的 {name}被环境变量中对应名称的值替代。

返回最后一次访问path的时间，返回值的格式为一个float类型的数值，表示距离epoch基准时间1970-01-01 00：00：00的秒数。如果path表示的路径不存在或者没有权限，抛出异常OSError。

返回最后一次修改path的时间，返回值的格式为一个float类型的数值，表示距离epoch基准时间1970-01-01 00：00：00的秒数。如果path表示的路径不存在或者没有权限，抛出异常OSError。

返回path表示的文件或路径的大小，以byte字节为单位。如果path表示的路径不存在或者没有权限，抛出异常OSError。

如果path是绝对路径，返回True，否则返回False。

如果path表示的是已存在的文件路径，返回True。

如果path表示的是已存在的目录，返回True。

如果path表示的是链接，返回True。

判断path是否为挂载点。

连接一个或多个路径，path和多个*paths的连接会使用路径分隔符。

对path的字母大小写进行normalize。在Windows系统中，path中的所有字母都转成小写，并且把正斜杠转成反斜杠。在其他操作系统中，返回path本身。

对path进行normalize，删除多余的路径分隔符。

split the path into a pair (head, tail)，其中tail是path中最后的部分，并且永远不会含有斜杠，head是除了tail之外的部分。如果path以斜杠结尾，tail为空；如果path中不包含斜杠，head为空；如果path为空，head和tail都是空。

㈧ 两个字符串的最长公共子串python代码

最长公共子串（Longest Common Substring）： 是指两个字符串中最长连续相同的子串长度。
例如：str1=“1AB2345CD”,str2=”12345EF”,则str1，str2的最长公共子串为2345。

㈨ 寻找字符串数组的最长公共子串

所谓最长公共子串问题是寻找两个或多个已知字符串最长的子串。例如字符串 “ABCD”与“ABCDE”、“FABCDE”的最长公共子串是“ABCD”……

值得注意的是，有些人把最长公共子序列、最长公共前缀与最长公共子串搞混淆了，请特别注意⚠️。

《高效算法：竞赛、应试与提高必修128例》中介绍了最长公共子串的算法，不过只是找两个字符串之间的最长公共子串， 并没有给出任意个数 （此处当然指的是3个或以上）字符串的最长公共子串的求法。

现在用Python试写如下：

最长子串还可以用lamada写法，看起来更加简洁

这个方法的复杂度是 O(n1 x n1 x (n1 + ... + nK)) ， 如果字符串不复杂，还是可以一用的😄。

㈩ Python浅薄的基础小结上

Python 支持四种不同的数值类型：

整型(Int) - 通常被称为是整型或整数，是正或负整数，不带小数点。

长整型(long integers) - 无限大小的整数，整数最后是一个大写或小写的L。

浮点型(floating point real values) - 浮点型由整数部分与小数部分组成，浮点型也可以使用科学计数法表示（2.5e2 = 2.5 x 102= 250）

复数(complex numbers) - 复数由实数部分和虚数部分构成，可以用a + bj,或者complex(a,b)表示， 复数的实部a和虚部b都是浮点型。

在Phton中常见的运算加、减、乘、除、求余、幂指数等，同现实生活中的遵循一样的优先级。即，乘除运算高于加减运算。例：

Python内置复数的计算支持所有常见复数的计算，对复数处理的数学函数在模块cmath中：

字符串或串(String)是由数字、字母、下划线组成的一串字符。Python字符串最大的特点是 不可修改， 只能生成新的字符串，用 双引号或单引号 都可以表示字符串，多行字符串用三个连续单引号表示，特殊字符用转义符 “\" 表示如： 制表符"\t",换行符"\n"

>>>str='Hello World!'

>>>print  str*2   # 输出字符串两次

Hello World!Hello World!

>>>print  str+"TEST"   # 输出连接的字符串

Hello World!TEST

>>>len('str')   #输出字符串的长度

12

python的 字串行表 有2种取值顺序:

从左到右索引默认0开始的，最大范围是字符串长度少1

从右到左索引默认-1开始的，最大范围是字符串开头

如果你要实现从字符串中获取一段子字符串的话，可以使用变量 [头下标:尾下标] ，就可以截取相应的字符串，其中下标是从 0 开始算起，可以是正数或负数，下标可以为空表示取到头或尾。比如:

s = 'ilovepython'

s[1:5] 的结果是 love。

当使用以冒号分隔的字符串，python返回一个新的对象，结果包含了以这对偏移标识的连续的内容，左边的开始是包含了下边界。

上面的结果包含了s[1]的值l，而取到的最大范围不包括上边界，就是s[5]的值p。

'abcd'[3:1:-1]  #从右到左

'dc'

一些高级操作：

>>>s='You are my sunshine'

>>>s.split(' ')

['You' ,'are', 'my' ,'sunshine']

>>>t=['one','for','two']

>>>' '.join(t)

'one for two'

>>>t='Mike and Tom'

>>>t.replace('Tom','jane')

'Mike and jane'

python变量的概念和初中代数的方程变量一致，变量就像贴在东西上的标签，命名规则：大小写英文、数字和下划线，且不能用数字开头，变量可以反复赋值，而且可以是不同类型的变量

序列是Python中最基本的数据结构。序列中的每个元素都分配一个数字 - 它的位置，或索引，第一个索引是0，第二个索引是1，依此类推。

Python有6个序列的内置类型，但最常见的是列表和元组。

序列都可以进行的操作包括索引，切片，加，乘，检查成员。

此外，Python已经内置确定序列的长度以及确定最大和最小的元素的方法。

列表 是最常用的Python数据类型，它可以作为一个方括号内的逗号分隔值出现。

列表的数据项不需要具有相同的类型

创建一个列表，只要把逗号分隔的不同的数据项使用方括号括起来即可。

>>>[]  #创建空的列表

[]

>>>list() #创建空的列表

[]

>>>alist=['physics','chemistry',1997,2000]

['physics','chemistry',1997,2000]

List（列表） 是 Python 中使用最频繁的数据类型。

列表可以完成大多数集合类的数据结构实现。它支持字符，数字，字符串甚至可以包含列表（即嵌套）。

列表用[ ]标识，是 python 最通用的复合数据类型。

列表中值的切割也可以用到变量[头下标:尾下标]，就可以截取相应的列表，从左到右索引默认 0 开始，从右到左索引默认 -1 开始，下标可以为空表示取到头或尾。

>>>list=['runoob', 786, 2.23, 'john', 70.2]

>>>tinylist=[123, 'john']

>>>print list  # 输出完整列表

['runoob', 786, 2.23, 'john', 70.2]

>>>'runoob' in alist  #某个元素是否存在

True

>>>print list[0]   # 输出列表的第一个元素

runoob

>>>print list[1:3]   # 输出第二个至第三个元素

[786,2.23]

>>>print list[2:]   # 输出从第三个开始至列表末尾的所有元素

[2.23,'john',70.2]

>>>print tinylist*2   # 输出列表两次

[123,'john',123,'john']

>>>print list+tinylist   # 打印组合的列表

['runoob',786,2.23,'john',70.2,123,'john']

Python的元组 与列表类似，不同之处在于元组的元素不能修改。

元组使用小括号，列表使用方括号。

元组创建很简单，只需要在括号中添加元素，并使用逗号隔开即可。

>>>()  #创建空的元组

()

>>>tuple()  #创建空的元组

()

元组中只包含一个元素时，需要在元素后面添加逗号如：tup1=(50,);

>>>tup=(1,True,0.234,"holle")

同列表相似 元组 适用：

+ ：链接两个元组

* ：复制n次，生成新的元组

in ：某个元素是否存在

[start:end:step] ：切片

值得注意的是元组是不可以更新的（ 不可变） 序列，但我们可以对元组进行连接组合生成新的元组如：

>>>tup1=(12,34.56)

>>>tup2=('abc','xyz')

>>>tup3= tup1+tup2

>>>print tup3

(12,34.56,'abc','xyz')

任意无符号的对象，以逗号隔开，默认为元组。

字典是另一种可变容器模型，且可存储任意类型对象。

字典的每个键值(key=>value)对用冒号( : )分割，每个对之间用逗号( , )分割，整个字典包括在花括号( {}) 中 ,格式如下所示：

d= {key1:value1,key2:value2}

键必须是唯一的，但值则不必。

值可以取任何数据类型，但键必须是不可变的，如字符串，数字或元组。

字典是可变类型，可以添加，删除，替换