python数据结构——字符串篇_数据结构长度从0开始吗

概念复习

1、字符

结构简单的语言文本，即是某种（或某些）自然语言中基本的文字符号构成的序列。
基本文字符号

2、字符集

有穷的一组字符构成的集合

3、字符序

字符集里的字符定义的一种顺序

4、字符串(串)

可看做特殊的线性表
ASCI， Unicode，
python字符串实现是一种不变数据类型（另一种实现是可变数据类型）

5、字符串长度

字符串里字符的长度

6、空串

长度为0的串

7、字符的位置(下标)

从0开始算起

8、字符串相等

9、字典序

从左向右查看两个串中下标相同的各对字符，遇到的第一对不同字符的字
符序决定了这两个字符串的顺序；另外，如果两个串中相同下标的各对字符都相同，但
其中一个串较短，那么就认为它较小，排在前面。举例说，考虑英文字母的集合，字
符序采用字母表中的顺序abcd…。这样就有字符串abc小于add，也小于abcd，因为虽
然abc和abd的前3个字符相同，但后者较长。

10、拼接

两个串拼接得到另一个串，python是用+，s1+s2

11、子串

s2包括了s1,s1就是子串

12、子串的出现位置

第一个字符的位置

13、前缀和后缀

如果存在字符串 $s^{{}^{\prime }}$, $s_2=s_1+s^{{}^{\prime }}$，则$s_1$为$s_2$的前缀，如果$s_2=s^{{}^{\prime }}+s_1$,则$s_1$是$s_2$的后缀。空串即是前缀，也是后缀。

14、串的幂

串s的n次幂是连续的n个s拼接而成的串

15、串替换

必须规定替换的顺序，从左到右还是从右到左。

16、python字符串

str是一个不变类型，创建后内容和长度都不变化，不同str对象的长度不同。
str对象操作分为两类：

• 获取str的信息
• 基于已有的str构造新的str对象。

考虑字符串的表示时，要确定两个方面：

• 字符串内容的存储。这里有两个极端：①把一个字符串的全部内容存储在一块连续存储区里；
• ②把串中每个字符单独存入一个独立存储块，并将这些块链接起来。连续存储的主要问题是需要大块存储，极长的字符串可能带来问题；而一个字符一块存储，需要附加一个链接域，额外存储开销比较大。实际中完全可以采用某种中间方式，把一个串的字符序列分段保存在一组存储块里，并链接起这些存储块。
• 字符串结束的表示。不同字符串的长度可能不同，如果采用连续表示方式，由于存储在计
  算机里的都是二进制编码，从存储内容无法判断哪里是串的结束。所以，必须采用某种方式表示字符串的结束。这里也有两种基本方式：①用一个专门的数据域记录字符串长度，就像前面连续表中的num域；②用一个特殊编码表示串结束，为此需要保证该编码不代表任何字符。C语言的字符串采用了第2种方式

17、 朴素匹配算法

def naive_matching(t, p):
'''
t:source
p：model 
'''
    m, n = len(p), len(t)
    i, j = 0, 0
    while i < m and j < n:
        if p[i] == t[j]:
            i, j = i + 1, j + 1
        else:
            i, j= 0, j - i + 1
        if i == m:
            return j - i
        return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

分析：
时间复杂度 $O(m\times n)$
每次把字符比较看做完全独立的操作，没有利用字符串的特点。

18、无回溯串匹配算法(KMP算法)

18.1 算法介绍

图为朴素匹配与KMP匹配过程

对于每个匹配字符串，先计算每个字符对应的移动位移，可记为pnext表，就是对于每个匹配字符串里的每个字符，下次匹配的字符。

def matching_KMP(t, p, pnext):
'''
t: source str
p: model str
'''
    j, i = 0, 0
    n, m = len(t), len(p)
    while j < n and i < m:
        if i == -1 or t[j] == p[i]:
            j, i = j+1, i + 1
        else:
            i = pnext[i]
        if i == m:
            return j - i
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

18.2 构造pnext表

思路解析

对模式串p中每个i，都有与之对应的下标$k_i$，与被匹配的目标串无关。
表元素pnext[i]记录与$i$对应的$k_i$的值。

表pnext的分析构造如图：
找到一个位置k，下次匹配用$p_k$与前面匹配失败的$t_j$比较，也就是模式串一道$p_k$与$t_j$对准的位置。确定k的问题就变成了确定$p_0,...p_{i-1}$的相等前缀和后缀的长度。$k$值越小表示移动得越远（也就是匹配得越少）。
如果$p_0...p_{i-1}$的最长相等前后缀的长度为，$k,(0\le k<i-1)$，$p_i\ne t_j$时，模式串就应该右移$i-k$位。也就是pnext[i]设置为k。
因此对模式串的每个位置i，求出模式串的子串$p_0...p_{i-1}$的最长相等前后缀的长度。

递推算法计算最长相等前后缀

假设pnext[i-1]的计算结果为k-1，比较$p_i$与$p_k$，有两张情况：

• 如果$p_i=p_k$,对于i的最长相等前后缀长度，比对i-1的最长相等前后缀的长度多1，这是pnext[i]设置为k，继续检查下一个；
• 否则把$p_0...p_{k-1}$的最长相等前缀移过来检查。
• 可以尝试分析字符串 $abaeeabafe$的pnext表

一直pnext[0] = -1和直至pnext[i-1]的已有值求pnext[i]的算法：

def gen_pnext(p):
'''
generate check table for each char in p
use for KMP
'''
    i, k, m = 0, -1, len(p)
    pnext = [-1] * m
    while i < m - 1:
        if k == -1 or p[i] == p[k]:
            i, k = i + 1, k + 1
            pnext[i] = k
        else:
            k = pnext[k]
    return pnext
1
2
3
4
5
6
7
8
9
10
11
12
13

这个算法的时间复杂性是$O(m)$,m是模式串的长度。

改进的pnext表构造算法

pnext的分析构造图可以看出，匹配失败时有$p_i\ne t_j$, 设$pnext[i]=k$,如果发现$p_i=p_k$, 那么一定也有$p_k\ne t_j$.这种情况下，模式串应该右移到pnext[k]（而不是右移到pnext[i]），下一步应该用$p_{next[k]}$与$t_j$比较。这一修改可以把模式串右移更远。

def gen_pnext(p):
    i, k, m = 0, -1, len(p)
    pnext = [-1] * m
    while i < m - 1:
        if k == -1 or p[i] == p[k]:
            i, k = i + 1, k + 1
            if p[i] == p[k]:
                pnext[i] = pnext[k]
            else:
                pnext[i] = k
        else:
            k = pnext[k]
     return pnext
1
2
3
4
5
6
7
8
9
10
11
12

算法分析

KMP算法包括：构造pnext表和匹配。如果模式串和目标串的长度分别为$m$和$n$，KMP算法时间的复杂性是$O(m+n)$，通常情况下 $m<<n$,因此可认为算法的复杂性为$O(n)$，显然优于朴素匹配算法的$O(m\times n)$

19 字符串匹配问题

19.1模式

一个模式描述了（能匹配）一些字符串（一个字符串集合)
对于一般的模式，都需要注意三个问题：模式的形式是什么，描述的字符串集合如何确定，怎样做匹配
描述能力越强，需要的匹配算法负复杂性越高

19.2 通配符

*所有字符串
？一个字符串

19.3 正则表达式

理论的正则表达式如下定义，其中$\alpha$和$\beta$都是正则表达式：

• 正则表达式的普通字符只与该字符本身匹配
• 顺序组合 $\alpha \beta$,如果$\alpha$能匹配$s$，$\beta$ 能匹配$t$，那么$\alpha \beta$表示的就是$s+t$
• 选择组合$\alpha |\beta \alpha$:如果$\alpha$能匹配 $s$，$\beta$能匹配$t$, $\alpha |\beta \alpha$,表示既能匹配$s$,又能匹配$t$。
• 星号$\alpha \ast$：如果$\alpha$能匹配字符串$s$,则$\alpha \ast$表示能匹配空串、$s$,$s+s$,$s+s+s$，也就是能与0或任意多段s拼接串匹配

举例：
abc，只匹配abc
a(b*)(c*)与所有保号一个a之后任意多个b，再之后任意多个c的串匹配
a((b|c)*)与所有在一个a后出现任意多个b和c的串匹配

19.4 一种简化的正则表达式

模式语言，介绍一种简化的正则表达式：

• 任一符号仅与其本身匹配
• 圆点符号"."匹配任意字符
• 符号“^“只匹配目标串的开头，不匹配任何具体字符
• 符号“$”只匹配目标串的结束，不匹配任何具体字符
• 符号“*”表示其前面那个字符课匹配0个或任意多个相同的字符

其中“^“和”$"符号至多在模式的开始和结束出现一次

举例：
p1 = “ab.”
p2 = “^abc.$"
p3 = "aabc.bca”

匹配算法：

def match(re, text):
 def match_here(re, i, text, j):
  """
   text begin from index j
   re begin from index i
  """
  while True:
   if i == rlen:
    return True
   if re[i] == '$':
    return i + 1 == rlen and j == tlen
   if i + 1 < rlen and re[i + 1] == '*':
    return match_star(re[i], re, i+2, text, j)
   if j == tlen or (re[i] != '.' and re[i] != text[j]):
    return False
   i, j = i + 1, j + 1
  def match_star(c, re, i, text, j):
  """
   Skip 0 or more c in text
  """
  for n in range(j, tlen):
   if match_here(re, i, text, n):
    return True
   if text[n] != c and c != '.':
    break
  return False
 rlen, tlen = len(re), len(text)
 if re[0] == '^':
  if match_here(re, 1, text, 0):
   return 1
 for n in range(tlen):
  if match_here(re, 0, text, n):
   return n
 return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

20.Python正则表达式

python正则表达式功能由标准包re提供。
一个具有正则表达式形式的字符串代表一个字符串模式，描述了一个特定的字符串几何。
re包的正则表达式实际上构成了一个特殊的小语言：

• 语法：re包规定的一套特殊描述规则
• 语义：一个正则表达式所描述的字符串集

20.1 原始字符串

普通字符串魏子良：str类型的字符串对象
原始字符串的形式，加r或R:

R"abcdefg"
r"C:\courses\python\progs"

""不代表转义字符

20.2 元字符（特殊字符）

re里面有14个：

. ^ $ * + ? \ | { } [ ] ( )

20.3 主要操作

说明：pattern表示模式串（正则表达式的字符串），string表示被处理的字符串，repi表示替换串，即操作中使用的另一个字符串。

• 生成正则表达式对象：

import re
# re.compile(pattern,flag = 0)
r1 = re.compile('abc')
1
2

生成与‘abc’对应的正则表达式对象，赋值给r1

• 检索

# re.search(patern, string,flag=0)
re.search('abc','aeabced',1)
<_sre.SRE_Match object; span=(2, 5), match='abc'>
1
2

• 匹配

# re.match(pattern,string,flag=0)
>>> r1 = re.match('abc','aeabced',1)
>>> r1
>>> r1 = re.match('abc','abc',1)
>>> r1
<_sre.SRE_Match object; span=(0, 3), match='abc'>
1
2
3
4
5

• 分割

# re.split(pattern,string,maxsplit=0,flags=0)
re.split(' ','abc abc are not the same')
['abc', 'abc', 'are', 'not', 'the', 'same']
1
2

• 找出所有匹配串

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

20.4 正则表达式的构造

注意两点：

• 一种表达式(或者元符号)的描述形式(构造形式)。
• 这种表达式能匹配怎样的字符串(集合)。

字符组：与一组字符中任何一个字符匹配

• 字符中描述符[…]：与方括号中列出的字符序列中的任一字符匹配。字符组里字符排列顺序不重要，比如[abc]可以与a或b或c匹配。
  其他形式：
  区间形式：[0-9]匹配所有的十进制数字字符。数字、字母区间，比如[34ad-fs-z]，[0-9a-zA-Z]匹配所有的数字字母
  特殊形式${[}^{.}..]$对^之后列出的字符组求补。比如 ${[}^0-9]$匹配非十进制数字的所有字符。

如果需要在字符组里包括字符KaTeX parse error: Expected group after '^' at position 1: ^̲,就不能把它放在第一个位置，也可以放在后面，或者写"^",如果字符组需要包括”-“，"]",必须写"-","]"

• 圆点字符[.]：通配符，匹配任何字符

a…b匹配所有a开头b结尾的四字字符
re采用转义串的形式定义了一些常用字符组，包括：

• \d: 十进制数字匹配
• \D:非十进制数字的所有字符匹配${[}^0-9]$
• \s: 所有空白字符匹配，等价于KaTeX parse error: Undefined control sequence: \t at position 3: [ \̲t̲ ̲\v \n \f \r]
• \S:所有非空白字符匹配
• \w:所有字母数字字符匹配
• \W:所有非字母数字字符匹配

重复

• 重复描述符，re里面用“*”，

re.split('a*','abbaaabbdbbabbababbabb')
['', 'bb', 'bbdbb', 'bb', 'b', 'bb', 'bb']
1

re.match(‘ab*’,‘abbbbbbbc’)可以与字符串里的a匹配，也可以与ab匹配。一般正则表达式匹配都提供了两种可能：

• 贪婪匹配：与最长的子串匹配，abbbbbbb.re规定“*”做贪婪匹配
• 非贪婪匹配（吝啬匹配）：匹配最短子串

与“*”略不同的是“+”，表示作用模式的1次货多次重复，至少要一次
描述正整数的一个简单模式是‘\d+’,等价于，“\d\d *”

可选描述符

‘？’
比如’a?‘可以与空串货与a匹配的字符串匹配。要求与a匹配的字符串的0或1次重复匹配
描述整数的一种简单模式‘-？\d+’

重复次数描述符

确定次数的重复用{n}描述，a{n}与a匹配的串的n次重复匹配

背景固话号码的模式串可以写’(010-)?[2-9][0-9]{7}‘,010-开始，随后是数字2-9，再后是7个十进制数字。（010-）？表示整个字段可选

重复次数的范围描述符{m,n}

a{m,n}与a匹配的串的m到n此重复匹配，其中包括m次和n次
a{3,7}与3到7个a构成的串匹配
go{2,5}gle与google,gooogle,goooogle,gooooogle匹配。

a{n}等价于a{n,n}
a?等价于a{1, infinity}
*,+,?,{m,n}都才去贪婪匹配规则

非贪婪匹配描述符，加一个？
*? ?? +? {m,n}?

选择 |

描述两种或多种情况之一的匹配。
a|b|c可以匹配a或者b或者c，[abc]是其简写。
’0|[1-9]\d*'可以匹配python语言里的十进制整数。（python负号看做运算符，非0整数不能以0开头）。这个模式会与0123的0匹配，与abc123,a123b的123匹配。他们在程序里不看做整数，都需要排除。
匹配国内固定电话号码模式：‘0\d{2} -\d{8}|0\d{3}-d{7,8}

首尾描述符

• 行首描述符："^"开头，只与一行的前缀子串匹配。
• 行位描述符："$"符号结尾。
• 串首描述符：\A
• 串尾描述符：\Z
  14个元字符：三对括号，分别用于优先级结合、字符组和重复次数、原点是通配符、星号和加号表示重复，^和$表示行首和行尾，反斜线符号转义符。

单词边界

\b 在实际单词边界位置匹配空串（不匹配实际字符）。胆子是字母数字的任意连续序列，边界就是非字母数字的字符或者无字符（串的开头/结束）
python里面\b是退格符，re里面是单词边界，解决方法有两个

• 将模式串里的\双写，表示把\本身送给re.compile等函数。例如’\b123\b\讲不匹配abc123a里面的123，但是匹配（123，123）里面的123。
• 用python原始字符串，其中的\不转义，上面模式可写成r’\b123\b’
  整数模式’\b(0+|[1-9]\d*)\b’,用原始字符串形式简单写r’\b(0+|[1-9]\d*)\b’。
  带正负号’[±]?\b(0+|[1-9]\d*)\b’

找出字符串里面所有整数，计算他们的和

def sumInt(s):
 re_int = r'\b(0|[1-9]\d*)\b'
 if s == None:
  return 0
 int_list = map(int, re.findall(re_int, s))
 print(int_list)
 s = 0
 for n in int_list:
  s+= n
 return s

sumInt('adfas 1 2 dafsdf 4 dfa 56')
<map object at 0x000001A3DFA320B8>
1
2
3
4
5
6
7
8
9
10
11
12

转义元字符\B是\b的补，匹配空串，但是要求在相应位置是字母或者数字

 re.findall('py.\B', 'python, py 2, py342py1py2py4')
Out[41]: ['pyt', 'py3', 'py1', 'py2']
1

匹配对象（match对象)

匹配操作的结果可用于逻辑判断
取得被匹配的子串：mat.group()。通过匹配成功得到了mat,所用的正则表达式自然与目标串的一个子串成功匹配

模式里的组（group）

mat = re.search('.((.)e)f','abcdef')
mat
<_sre.SRE_Match object; span=(2, 6), match='cdef'>
mat.group(0)
Out[46]: 'cdef'
mat.group(1)
Out[47]: 'de'
mat.group(2)
Out[48]: 'd'
#mat.group(3) no such group
1
2
3
4
5
6
7
8
9
10

r’(.{2}) \1’匹配前两个字符后，是空号，然后下两个要跟前面两个一样。普通字符串里\1表示二进制编码为1de zifu 0*01，故也可以写成’(.{2}) \1’

其他匹配操作

• re.fullmatch(pattern,string,flags = 0),成功，匹配成功信息的match对象，不成功，None
• re.finditer(pattern,string,flags=0),顺序取得个非重叠匹配得的match对象
• re.sub(pattern,repl,string,count=0,flags=0)

正则表达式对象

用regex代表一个正则表达式对象，方括号括起的部分表示可选

• 检索：regex.search(string[, pos[,endpos]])
• 匹配：regex.match(string[,pos[,endpos]])
• 完全匹配：regex.fullmatch(string[,pos[,endpos]])
• regex.findall(string[,pos[,endpos]])
• regex.finditer(string[,pos[,endpos]])
• 切分：regex.split(string,maxsplit=0)
• 替换：regex.sub(repl, string, count=0)

正则表达式的使用

待续。。
Python原始字符串，元字符，常规字符，顺序组合(拼接)，字符组，重复模式，选择模式，
组概念。