《数据结构与算法 python语言描述》学习笔记（四）————字符串_字符串scksc具有多少个不相同的子串

第一部分：学习内容概要

• 字符集、字符串和字符串操作
• 字符串的实现
• 字符串匹配（子串查找）
• 字符串匹配问题
• Python正则表达式

第二部分：学习笔记

• 字符集、字符串和字符串操作
    1. 字符集就是有穷的一组字符构成的集合。
    2. 字符序是字符集里的字符上定义的一种顺序
    3. 字符串可以看做一类特殊的线性表，表中元素取自选定的字符集。
    4. 字符串抽象数据类型

ADT String:
	String(self,sseq)  		#基于字符序列sseq建立一个字符串
	is_empty(self)			#判断本字符串是否空串
	len(self)				#取得字符串的长度
	char(self,index)		#取得字符串中位置index的字符
	substr(self,a,b)		#取得字符串中[a:b]的子串，左闭右开区间
	match(self,string)		#查找串string在本字符串中第一个出现的位置
	concat(self,string)		#做出本字符串与另一字符串string的拼接串
	subst(self,str1,str2)   #做出将本字符串里的子串str1都替换为str2的结果串
1
2
3
4
5
6
7
8
9

• 字符串的实现
    Python的字符串
      str：串长度的len和定为访问字符为O(1)复杂度。其他操作都需要扫描整个串的内容都是O(n)复杂度。
• 字符串匹配（子串查找）
    1. 字符串匹配就是在t中查找与p相同的子串的操作。
    2. 串匹配和朴素匹配算法
    串匹配的关键：① 怎样选择开始比较的字符对；② 发现了不匹配后，下一步怎么做。
      朴素的串匹配算法：① 从左到右逐个字符匹配； ② 发现不匹配时，专区考虑目标串里的下一个位置是否与模式串匹配。
      无回溯串匹配算法（KMP算法）：①将不匹配的字符子串排除，从下一个位置开始继续匹配，直到匹配到或者匹配完为止。

def gen_pnext(p):
'''生成针对P中各位置i的下一个检查位置表，用于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
			if p[i] == p[k]:
				pnext[i] == pnext[k]
			else:
				pnext[i] = k
		else:
			k = pnext[k]
	return pnext

def matching_KMP(t, p, pnext):
	"""KMP串匹配，主函数"""
	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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

• 字符串匹配问题
    简化的正则表达式：
      1. 任一字符仅与其本身匹配
      2. 圆点符号“.”可以匹配任意字符
      3. 符号“^”只匹配目标串的开头，不匹配任何具体字符。
      4. 符号“$”只匹配目标串的结束，不匹配任何具体字符。
      5.符号“*”表示前面那个字符可匹配0个或任意多个相同字符。
• Python正则表达式
    元字符：.  ^  $ * +  ?  \ | ( ) [ ] { }
    主要操作：
      1. re.compole(pattern, flag=0) 生成正则表达式对象
      2. re.search(pattern, string, flag=0) 搜索
      3. re.match(pattern, string, flag=0) 匹配
      4. re.split(pattern, string, maxsplit=0, flag=0) 分割
      5. re.findall(pattern, string, flag=0) 找出所有匹配串
      6. 常用字符组：\d：与十进制数字匹配，等价于[0-9]；
             \D：与非十进制数字匹配，等价于[^0-9]；
             \s：与所有空白字符匹配，等价于[\t\v\n\f\r]；
             \S：与所有非空白字符匹配，等价于[^\t\v\n\f\r]；
             \w：与所有字母数字字符匹配，等价于[0-9a-zA-Z]；
             \W：与所有非字母数字字符匹配，等价于[^0-9a-zA-Z]；
    

第三部分：课后练习

1. 复习
2. 字符串abcdab有多少个不同的子串？请列出它的所有前缀和后缀（子串）。
   答：
     有15个不同的子串。{a, b, c, d, ab, bc, cd, da, abc, bcd, cda, dab, abcd, abcda, abcdab}
3. 请用Python正则表达式描述下面模式：
     a）你所在学校的学号；[1][5678][0-9]\d{6}
     b）身份证号码; r’^([1-9]\d{5}[12]\d{3}(0[1-9]|1[012])(0[1-9]|[12][0-9]|3[01])\d{3}[0-9xX])$’
4. 请用Python的正则表达式功能实现下面操作：
     a）选出一个浮点数数据文件中所用采用科学计数法表示的数据; .*\..*e[+|-](\d).*
     b) 找出网页里所有链接；r’^href:(.?)’
     c）找出一个Python文件中定义的所有全局函数名字。r’^def .($’