介绍

本节内容将介绍在 Python 里处理字符串的基本概念，以及正则表达式的使用，以及介绍几种常见的字符串处理算法。

知识点

• 字符串的基本概念
• 正则表达式
• KMP 算法
• 编辑距离
• manacher 算法

基本概念

字符串是 Python 中最常见的数据类型。我们可以使用引号 (' 或 ")来创建字符串。

创建字符串很简单，只要为变量分配一个值即可。例如：

var1='Hello shiyanlou'

Python 访问字符串中的值使用方括号来截取字符串，如下示例：

var2='Hello shiyanlou!'
print("var2[1:5]:",var2[1:5])

Python 字符串更新

可以截取字符串的一部分并与其他字段拼接

var3='Hello user!'
print("已更新字符串：",var3[:6],'user!')

执行结果: 已更新字符串：Hello user!

Python 转义字符

在需要在字符中使用特殊字符时，Python 用反斜杠(\) 转义字符。

Python 字符串运算符

Python 字符串格式化

Python 支持格式化字符串的输出。尽管这样可能会用到非常复杂的表达式，但最基本的用法是将一个值插入到一个有字符串格式符 %s 的字符串中

示例如下：

print("Hello user %d,Welcome to %s"%(34291615,"shiyanlou"))

输出结果：Hello user 34291615,Welcome to shiyanlou

Python 字符串格式化符号

正则表达式

正则表达式是一个特殊的字符序列，它能帮助你方便的检查一个字符串是否与某种模式匹配。re 模块使 Python 语言拥有全部的正则表达式功能。

re.match 函数

re.match 尝试从字符串的起始位置匹配一个模式，如果不是起始位置匹配成功的话，match()就返回 None

函数语法：

re.match(pattern,string,flags=0)

函数参数说明：

实例：

import re
print(re.match('www', 'www.shiyanlou.com').span())  # 在起始位置匹配
print(re.match('com', 'www.shiyanlou.com'))         # 不在起始位置匹配

以上实例运行输出结果为：

(0,3)
None

re.search 方法

re.search 扫描整个字符串并返回第一个成功的匹配

函数语法：

re.search(pattern,string,flags=0)

函数参数说明：

实例：

import re
print(re.search('www', 'www.shiyanlou.com').span())  # 在起始位置匹配
print(re.search('com', 'www.shiyanlou.com').span())   # 不在起始位置匹配

以上实例运行输出结果为：

(0,3)
(11,14)

re.match 与 re.search 的区别

re.match 只匹配字符串的开始，如果字符串开始不符合正则表达式，则匹配失败，函数返回 None；而 re.search 匹配整个字符串，直到找到一个匹配

检索和替换

Python 的 re 模块提供了 re.sub 用于替换字符串中的匹配项。

语法：

re.sub(pattern,repl,string,count=0,flags=0)

• pattern:正则表达式中模式字符串
• repl:替换的字符串，也可为一个函数
• string:要被查找替换的原始字符串
• count:模式匹配后替换的最大次数,默认 0 表示替换所有的匹配

import re
phone="2004-959-559 # 这是一个国外电话号码"

#删除字符串中的 Python注释
num=re.sub(r'#.*$',"",phone) #r代表正则表达式,将在后面介绍具体规则
print("电话号码是：",num)

# 删除非数字(-)的字符串 
num = re.sub(r'\D', "", phone)
print("电话号码是：",num)

执行结果如下：
电话号码是: 2004-959-559
电话号码是 : 200495955

recompile 函数

compile 函数用于编译正则表达式，生成一个正则表达（Pattern）对象，供 match() 和 search() 这两个函数使用。

语法格式为：

re.compile(pattern[,flags])

参数：

• pattern: 一个字符串形式的正则表达式
• flags:可选，表示匹配模式，比如忽略大小写，多行模式，具体参数为：
  • re.l 忽略大小写
  • re.L 表示特殊字符集 \w, \W, \b, \B, \s, \S 依赖于当前环境
  • re.M 多行模式
  • re.S . 并且包括换行符在内的任意字符（. 不包括换行符)
  • re.X 为了增加可读性，忽略空格和 # 后面的注释

findall

在字符串中找到正则表达式所匹配的所有子串，并返回一个列表，如果没有找到匹配的，则返回空列表。

语法：

findall(string[,pos[,endpos]])

参数：

• string:待匹配的字符串
• pos:可选参数，指定字符串的起始位置，默认为 0。
• endpos:可选参数，指定字符串的结束位置，默认为字符串的长度。

查找字符串中的所有数字：

import re
pattern=re.compile(r'\d+') #查找数字
result1 = pattern.findall('runoob 123 google 456')
result2 = pattern.findall('run88oob123google456', 0, 10)
print(result1)
print(result2)

输出结果：
['123','456']
['88','12']

re.split

split 方法按照能够匹配的子串将字符串分割后返回列表

语法如下：

re.split(pattern, string[, maxsplit=0, flags=0])

参数：

正则表达式实例

字符类

特殊字符类

KMP 算法

字符串匹配是极为常见的一种模式匹配。简单地说，就是判断主串 T 中是否出现模式串 P，即 P 为 T 的子串。特别地，定义主串 T[0...n-1],模式串为 P [0...p-1],则主串与模式串的长度各为 n 与 p

暴力匹配

暴力匹配方法的思想非常朴素：

1. 依次从主串的首字符开始，与模式串逐一进行匹配
2. 遇到失配时，则移到主串的第二个字符，将其与模式串首字符比较，逐一进行匹配
3. 重复上述步骤，直至能匹配上，或剩下主串的长度不足以进行匹配

参考代码如下：

def brute_force_match(t,p):
    tlen=len(t)
    plen=len(p)
    for i in range(tlen):
        j=0
        while t[i+j]==p[j] and j <plen:
            j=j+1
            if j==plen:
                return i
    return -1

算法复杂度分析：i 在主串上移动 (n-p)次，匹配失败时，j 移动次数最多有 p-1 次。因此复杂度为 O(n*p)

对于暴力匹配而言，就存在重复匹配的现象。比如，第一次匹配失败时，主串，模式串失败匹配的位置的字符分别为 a 与 c ,下一次匹配时主串，模式串的起始位置分别为 T1 与 P[0];而在模式串中 c 之前是 ab ,未有重复结构，因此 T1与 P[0]肯定不能匹配上，这样造成了重复匹配。直观上，下一次匹配应从 T2 与 P[0] 开始。

那么如何提高匹配效率呢？那就考虑下 KMP 算法

KMP 算法原理

KMP 详细证明

KMP 算法思想归纳如下：将主串 T 的第一个字符与模式串 P 的第一个字符进行匹配。如果相等，则依次比较 T 和 P 的下一个字符。如果不相等，则 主串 T 移动(已匹配字符数-对应的部分匹配值)位，继续匹配。

关于移动位数的解释：已匹配字符数，即当前已完成匹配的字符数量。部分匹配值就是前缀和后缀的最长的共有元素的长度。

前缀指除了最后一个字符以外，一个字符串的全部头部组合

后缀指除了第一个字符以外，一个字符串的全部尾部组合

举个例子：以"ABCDABD"为例

• "A"的前缀和后缀都为空集，共有元素的长度为 0；
• "AB"的前缀为[A]，后缀为[B]，共有元素的长度为 0；
• "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度 0；
• "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为 0；
• "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为 1；
• "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为 2；
• "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为 0。

部分匹配表如下：

作业

请根据 KMP 算法原理，编写 kmp 算法实现字符匹配吧。

主串:123456456

目标串:123456

在/home/shiyanlou/下新建一个文件kmp.py。

参考代码

注意：请务必自己独立思考解决问题之后再对照参考答案，一开始直接看参考答案收获不大。

参考代码如下：

def get_failure_array(pattern): #制作部分匹配表
    failure = [0]
    i = 0
    j = 1
    while j < len(pattern):
        if pattern[i] == pattern[j]:
            i += 1
        elif i > 0:
            i = failure[i-1]
            continue
        j += 1
        failure.append(i)
    return failure
def kmp(pattern, text):
    failure = get_failure_array(pattern) #得到部分匹配表
    i=0
    j=0
    while i < len(text):
        if pattern[j] == text[i]:
            if j == (len(pattern) - 1):
                return True
            j += 1
        elif j > 0:
            j = failure[j - 1]
            continue
        i += 1
    return False
if __name__=="__main__":
    print(kmp('123456','123123456'))

编辑距离

编辑距离(levenshtein distance)是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个（或哪几个）是比较可能的字。DNA 也可以视为用 A、C、G 和 T 组成的字符串，因此编辑距离也用在生物信息学中，判断二个 DNA 的类似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。

注：定义来自百度百科

算法原理

编辑距离允许的编辑操作有三种，如果字符相等，我们还可以选择不操作。我们可以列举一下这四种操作的情况。

1. 不操作：对于"ay"与"day"的 "y"字符，可以选择不操作。即"ay"与"day"之间的利文斯顿距离等于"a"和"da"之间的利文斯顿距离。

2. 替换操作：对于"day"与"dae"的最后一位字符"y"和"e"字符,可以选择进行替换操作。即"day"与"dae"之间的利文斯顿距离等于"da"和"da"之间的利文斯顿距离加上一。

3. 插入操作：对于"dae"与"da"的最后一位字符"e"和"a"字符,可以选择进行插入操作。即"dae"与"da"之间的利文斯顿距离等于"da"和"da"之间的利文斯顿距离加上一。

4. 删除操作：对于"dae"与"daey"的最后一位字符"e"和"a"字符,可以选择进行删除操作。即"dae"与"daey"之间的利文斯顿距离等于"dae"和"dae"之间的利文斯顿距离加上一。

作业

请根据 levenshtein 算法原理，编写 levenshtein 函数实现比较两个字符串的编辑距离。

例子如下：

>>> levenshtein_distance("planet", "planetary")
3
>>> levenshtein_distance("", "test")
4
>>> levenshtein_distance("book", "back")
2
>>> levenshtein_distance("book", "book")
0
>>> levenshtein_distance("test", "")
4
>>> levenshtein_distance("", "")
0
>>> levenshtein_distance("orchestration", "container")
10

在/home/shiyanlou/下新建一个文件levenshtein_distance.py。

参考代码如下：

注意：请务必自己独立思考解决问题之后再对照参考答案，一开始直接看参考答案收获不大。

def levenshtein_distance(first_word,second_word):
    if len(first_word)<len(second_word):
        return levenshtein_distance(second_word,first_world)
    if len(second_word)==0:
        return len(first_word)
    previous_row=range(len(second_word)+1)
    for i,c1 in enumerate(first_word):
        current_row=[i+1]
        for j,c2 in enumerate(second_word):
            # 计算增加，删除，修改次数
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            # 得到最小值，添加到current_row
            current_row.append(min(insertions, deletions, substitutions))
        # 储存previous_row
        previous_row = current_row
    #返回最后的编辑距离
    return previous_row[-1]

最长回文字串

所谓回文字串，即正着读和倒着读结果都一样的字符串,比如:a, aba, abccba 都是回文串,ab, abb, abca 都不是回文串。

暴力求解的思路：找到字符串的所有子串，遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定，因此对于一个长度为 n 的字符串，共有 n^2 个子串。这些子串的平均长度大约是 n/2，因此这个解法的时间复杂度是 O(n^3)。我们能不能提高效率呢，当然可以。这里给大家介绍马拉车算法。

求解回文串的问题，有很多巧妙的求解算法，这里仅介绍马拉车算法，其他求解算法无法一一介绍，感兴趣的同学请自行探索。

马拉车算法

马拉车算法(Manacher)由一个叫 Manacher 的人在 1975 年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性，这是非常了不起的。让我们来看下马拉车算法的优越性在哪。

(1) 解决长度奇偶性带来的对称轴位置问题:Manacher 算法首先对字符串做一个预处理，在所有的空隙位置(包括首尾)插入同样的符号，要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的。以插入#号为例：

aba->#a#b#a#
abba->#a#b#b#a#

插入的是同样的符号，且符号不存在于原串，因此子串的回文性不受影响，原来是回文的串，插完之后还是回文的，原来不是回文的，依然不会是回文的。

(2) 解决重复访问的问题:我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。Manacher 定义了一个回文半径数组 RL，用 RL[i]表示以第 i 个字符为对称轴的回文串的回文半径。我们一般对字符串从左往右处理，因此这里定义 RL[i]为第 i 个字符为对称轴的回文串的最右一个字符与字符 i 的距离。对于上面插入分隔符之后的两个串，可以得到 RL 数组。

char:    # a # b # a #
RL  :    1 2 1 4 1 2 1
RL-1:    0 1 0 3 0 1 0
i   :    0 1 2 3 4 5 6

char:    # a # b # b # a #
RL  :    1 2 1 2 5 2 1 2 1
RL-1:    0 1 0 1 4 1 0 1 0
i   :    0 1 2 3 4 5 6 7 8

上面我们还求了一下 RL[i]-1。通过观察可以发现，RL[i]-1 的值，正是在原本那个没有插入过分隔符的串中，以位置 i 为对称轴的最长回文串的长度。那么只要我们求出了 RL 数组，就能得到最长回文子串的长度。

于是问题变成了，怎样高效地求的 RL 数组。基本思路是利用回文串的对称性，扩展回文串。

我们从左往右地访问字符串来求 RL，假设当前访问到的位置为 i，即要求 RL[i]，在对应上图，i 必然是在 po 右边的(obviously)。但我们更关注的是，i 是在 MaxRight 的左边还是右边。我们分情况来讨论。

1） 当 i 在 MaxRight 的左边

我们知道，图中两个红色块之间（包括红色块）的串是回文的；并且以 i 为对称轴的回文串，是与红色块间的回文串有所重叠的。我们找到 i 关于 pos 的对称位置 j，这个 j 对应的 RL[j]我们是已经算过的。根据回文串的对称性，以 i 为对称轴的回文串和以 j 为对称轴的回文串，有一部分是相同的。这里又有两种细分的情况。

a.以 j 为对称轴的回文串比较短

这时我们知道 RL[i]至少不会小于 RL[j]，并且已经知道了部分的以 i 为中心的回文串，于是可以令 RL[i]=RL[j]。但是以 i 为对称轴的回文串可能实际上更长，因此我们试着以 i 为对称轴，继续往左右两边扩展，直到左右两边字符不同，或者到达边界。

b.以 j 为对称轴的回文串比较长

这时，我们只能确定，两条蓝线之间的部分（即不超过 MaxRight 的部分）是回文的，于是从这个长度开始，尝试以 i 为中心向左右两边扩展，，直到左右两边字符不同，或者到达边界。

不论以上哪种情况，之后都要尝试更新 MaxRight 和 pos，因为有可能得到更大的 MaxRight。

具体操作如下：

1. 令 RL[i]=min(RL[2*pos-i], MaxRight-i)
2. 以 i 为中心扩展回文串，直到左右两边字符不同，或者到达边界
3. 更新 MaxRight 和 pos

2. 当 i 在 MaxRight 的右边

遇到这种情况，说明以 i 为对称轴的回文串还没有任何一个部分被访问过，于是只能从 i 的左右两边开始尝试扩展了，当左右两边字符不同，或者到达字符串边界时停止。然后更新 MaxRight 和 pos

参考代码如下；

def manacher(s):
    #预处理
    s='#'+'#'.join(s)+'#'

    RL=[0]*len(s)
    MaxRight=0
    pos=0
    MaxLen=0
    for i in range(len(s)):
        if i<MaxRight:
            RL[i]=min(RL[2*pos-i], MaxRight-i)
        else:
            RL[i]=1
        #尝试扩展，注意处理边界
        while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:
            RL[i]+=1
        #更新MaxRight,pos
        if RL[i]+i-1>MaxRight:
            MaxRight=RL[i]+i-1
            pos=i
        #更新最长回文串的长度
        MaxLen=max(MaxLen, RL[i])
    return MaxLen-1

总结

本节内容介绍在 Python 里处理字符串的基本概念，以及正则表达式的使用，以及如何解决字符串匹配问题，编辑距离，回文串问题，我们这里介绍了 kmp 算法,利文斯顿算法，马拉车算法。其实字符串还有很多比较复杂的问题，例如最长无重复子串，最长连续序列，验证数字等问题，这里不再详细介绍，如果大家感兴趣，请自行探索。回顾下本节内容主要包含了以下内容：

• 字符串的基本概念
• 正则表达式
• KMP 算法
• 编辑距离
• manacher 算法