1.
复习下面概念：字符，字符集，字符串（串），ASCII，Unicode，字符序，字符串长度，空串，字符的位置（下标），字符串相等，字典序，拼接，子串，子串的出现位置，前缀和后缀，串的幂，串替换，子串检索（子串匹配），Python的str类型，字符串匹配，模式匹配，目标串，模式串，朴素匹配算法，无回溯串匹配算法（KMP算法），模式，模式语言，描述能力与匹配算法的复杂性，通配符，正则表达式，正则表达式匹配，Python标准库re包，Python原始字符串，元字符，常规字符，顺序组合（拼接），字符组，重复模式，选择模式，组概念。
2.
字符串abcdab有多少个不同子串？请列出其所有前缀和后缀（子串）。
3.
找出模式串acba在目标串abccacbacbacabcabbacbbbbacbacbacb中的所有出现。
4.
请用Python正则表达式描述下面模式：
a)
你所在学校的学号
b)
你所在学校的职工号
c)
你所在城市的带区位号的固话号码
d)
身份证号码
e)
互联网的IP地址
f)
图书馆中计算机书籍的馆藏目录索书号的集合
注意：一般而言正则表达式描述的字符串集合是实际集合的超集，对于复杂的问题，通常无法给出相应字符串集合的精确描述，只需描述一个适当的超集。
5.
请利用Python的正则表达式功能实现下面操作
a)
选出一个浮点数数据文件中所有采用科学记数法表示的数据
b)
找出网页（html文件）里的所有链接
c)
找出一个Python文件中定义的所有全局函数名字
1.
针对Python的str对象，自己实现一个replace操作函数。
2.
定义生成器函数tokens(string, seps)，其中string参数是被处理的字符串，seps是描述分隔字符的字符串，都是str类型的对象。该生成器逐个给出string里一个个不包含seps中分隔字符的最大子串。
3.
请基于链接表的概念定义一个字符串类，每个链接结点保存一个字符。实现其构造函数（以Python的str对象为参数）。请定义下面方法：求串长度，完成字符串替换，采用朴素方式和KMP算法实现的子串匹配。
4.
为上述链接表字符串类增加下面方法：
a)
find_in(self,another)，确定本字符串中第一个属于字符串another的字符所在结点的位置，返回表示这个位置的整数；
b)
find_not_in(self,another)，与上面函数类似，但它要查找的是不属于another的字符；
c)
remove(self,another)，从self里删除串another里的字符。
5.
实际中经常需要在一个长字符串里查找与某几个字符串之一匹配的子串。请考虑这一问题并设计一个合理的算法，实现这个算法并分析其复杂性。
6.
请参考4.3.3节最后的建议，定义一个模式类，其构造函数基于一个字符串参数生成对象内部的pnext数组。修改KMP算法，使之使用这种模式对象。
7.
考虑一种字符串匹配方法：如果当前字符匹配成功则继续考虑下一字符，如果失败就将模式串右移一个位置继续匹配。经过连续的一些次成功匹配到达了模式串右端后，重新从模式串左端开始补足必要的字符匹配，直至确定完整一次模式串匹配。在这种匹配中的任何时候失败，总按上面的方式，继续用匹配失败的那个模式串字符与目标串的下一个字符比较。请开发这种想法，实现一个字符串匹配函数。
8.
R. S. Boyer和J. S. Moore提出了另一种串匹配算法，采用自右向左比较模式串字符的匹配方式，其中也用了一个失败匹配移动表。请基于这一想法深入分析，考虑如何实现一种字符串匹配算法（请自己查找相关材料）。
9.
在互联网wiki中有关字符串匹配的网页里描述了一些字符串匹配算法。请从中选出一种或几种其他算法，定义Python函数实现该算法。
10. 对4.4.2节的简化正则表达式做一点扩充：增加元字符
+ 表示前一字符的1次或任意多次重复，? 表示前一字符可选出现。请实现相应的匹配函数。