阅读裘宗燕老师的《数据结构与算法:python语言描述》的课件所记笔记

一、字符串相关概念

1.字符集

  • 字符是一个抽象概念,字符集是有穷的一组字符构成的集合
  • 标准字符集

2.字符串(简称串)

特殊线性表,表中元素取值选定的字符集,支持一组以串为对象的操作

3.串长度

  • 字符个数
  • 长度为0的串称为空串
  • 任意字符集里空串的唯一性

4.一般性

  • 每个字符的位置确定
  • 用0开始的自然数表示位置

5.串判断

  • 相等:长度相等,且对应位置的字符分别相等
  • 小于或大于:若第一个字符不相等,那就以第一个字符的比较结果为准,若第一个相等,那就比较第二个,以此类推。两串最终比较结果字符前的各字符应都对应相等。
  • 子串:存在S和S'使得S2 = S + S1 + S', 则S1是S2的字串
    • 1.子串也是串
    • 2.子串第一次出现时的第一个字符位置为子串出现的位置;
    • 3.子串可能多处出现,注意重叠情况不算
    • 4.空串是任何字符串的子串,任何字符串是本身的子串
  • 特殊子串:前缀是串开头的一段字符构成的子串,后缀是串最后的一段字符构成的子串

6.串运算

  • 拼接:S = S1 + S2。python里拼接用+表示
  • 幂:串s的n次幂是连续n个s拼接而成的串:s*n
  • 替换

7.代数结构

  • 空串是拼接操作的“单位元”(幺元)
    有结合律,无交换律
  • 串集合加上拼接操作,构成一个半群
    典型的半交换半群
  • 有单位元,因此是一个幺半群

二、字符串研究

1.串表示的两个问题

  • 串内容存储:1.连续存储。2.字符独立存储,链接起来
  • 串结束表示:1.专门数据域记录串长度。2.特殊符号表示结束

2.串替换

  • 子串多次出现
  • 多次出现可能重叠,只能规定一种代换顺序(如从左到右),一次代换破坏的子串不应再代入新串
  • 一次子串代换后,应从代入得新串之后继续工作。即使代入新串之后形成的部分能与子串匹配,也不应在本次替换中考虑

三、串匹配

1.算法设计的关键

  • 怎样比较字符
  • 发现不匹配后下一步怎么做

2.朴素匹配算法

  • 从左至右
  • 发现不匹配时,考虑目标串的下一位置
    def nmatching(t, p):
    i, j = 0, 0
    m, n = len(t), len(p)
    while i < m and j < n:
        if t[i] == p[j]:
            i, j = i+1, j+1
        else:
            i, j = i-j+1, 0
            # i=i-j+1, having matched i characters, but not matching string p. need to set the position after the first matched character for the next matching
    if j == n:
        return i-j
    return -1
  • 可能出现回溯:遇字符不相等时,目标串每次与模式串第一个字符作比较处的位置右移一个字符,并再次从p0(重置j=0后)开始比较
  • 最坏的情况是每趟比较都在最后出现不等,最多比较m-n+1趟,总共比较n(m-n+1),所有算法复杂度为nm

3.KMP算法

  • 核心思想:分析模式串,当在tj处不匹配时,充分利用模式串中已匹配字符的长度i来确定跳转到模式串中的pk其中0≤k<i)来与tj继续比较。
  • 例如模式串为abcac,若比较到模式串最后一个字符不匹配,这时目标串位置为tj的话,则tj继续与模式串中第二个b字符进行比较。因为模式串中第一个字符为a,而匹配的时候已确认tj前一个为a

解析:

  • 假设模式串匹配到p[i]时不匹配,实际上只是分析模式串中前缀子串p0...pi-1中的前缀子串po...px-1与后缀子串pi-x...pi-1的相等性及p[x]与p[i]是否相等。假定模式串为字符串s='abacabad',则可看其出前缀子串abaabacababacaba中的前后缀子串aababc的重复性,对应的p[i]分别为p[3]、p[6]、p[7]相应的p[x]分别为p[1]、p[2]、p[3]。当模式串匹配到p[3]即字符c不等时,与p[1]不等,因此可作跳转到p[1]继续比较;当匹配到p[6]即字符a时,由于与p[2]相等,不能跳转。
  • 假设模式串匹配到p[i]位置时不匹配,即判断前缀字串p[:y]与后缀字串p[i-y:i](0<y<i)是否匹配,选择最长的匹配,然后判断p[y]与p[i]是否相等,以ababac为例做分析

实现分析:

假设pnext[i]为位置i的跳转位置,其中0<=pnext[i]<i。匹配失败时,可能发现用pi之前的所有字符与tj比较都没有价值,下一步应该从头开始用P0与tj+1比较,这种特殊情况就在pnext[i]里记录-1,显然对于任何模式都有:pnext[0] = -1

代码如下:

def kmpmatch(t, p, pnext):
i, j = 0, 0
m, n = len(t), len(p)
while i < m and j < n:
    if i == -1 or t[i] == p[j]:
        i, j = i+1, j+1
    else:
        j = pnext[j]
if j ==n:
    return i-j
return -1
a.KMP算法pnext表分析
  • 当模式串匹配到pi不相等时,则计算p0...pi-1的最长相等的前后缀子串的长度,假设长度为k,则pnext[i]=k,即将模式串右移i-k个字符用pk去继续与tj比较
  • 等价于对每个i求p0...pi-1的最长相等前后缀子串的长度
b.pnext递推分析
  • 假设pnext[i]=k,则p0...pi-1的前缀子串p0...pk-1和后缀子串pi-k...pi-1相同,若pk与pi相同,则p0...pi的前缀子串p0...pk和后缀子串pi-k...pi相同,即pnext[i+1]=k+1。
  • 若pk与pi不相等,则试着在p0...pi-1中更短的前后缀相同子串中检查新的pk是否与pi相等,若相等,则pnext[i+1]=k+1

通过分析最长前后缀相同子串p0...pk-1和pi-k...pi-1可知,p0...pi-1中更短的前后缀相同子串必是p0...pk-1的最长前后缀相同子串,因此k=pnext[k],p[k]中的k代表p0...pi-1的最长相等前后缀子串长度,即每次p[k]与p[i]不相等就去最长前缀子串p0...pk-1找最长的前后缀相同子串长度k(即p[k]的pnext值pnext[k]),若新的p[k]值与p[i]还是不相等,则以此类推循环查找,直到pnext[k]=-1表示到了p0,此时退出循环。若循环中找到使得p[k]=p[i]的k值则退出循环。最后pnext[i+1]=k+1

  • 假设pnext[0]=x,p[0]前是空串,因此不作跳转,而p[1]一定会跳转到p[0]即pnext[1]=0,由上述pnext[i+1]=k+1分析可知,定义x=-1能保证循环的一致性,所以定义模式串所有位置p[i]的pnext默认值为-1,然后从i=0往后递推
  • 程序实现如下:
    def genPnext(p):
    i, k, m = 0, -1, len(p)
    pnext = [-1] * m
    while i < m-1:
    while k >= 0 and p[k] is not p[i]:
        k = pnext[k]
    i, k = i+1, k+1
    pnext[i] = k
    return pnext
  • 程序改进,当确认pnext[i]的值为k时,若p[k]与p[i]相同,则p[k]与tj也不相同,所以继续查找pnext[k]
    def genPnext(p):
    i, k, m = 0, -1, len(p)
    pnext = [-1] * m
    while i < m-1:
    while k >= 0 and p[k] is not p[i]:
        k = pnext[k]
    i, k = i+1, k+1
    if p[k] == p[i]:
        pnext[i] = pnext[k]
    else:
        pnext[i] = k
    return pnext

思考

推导pnext最关键的是循环在前一字符的最长前后缀字串中查找当前字符的最长前后缀字串

最后由 oucb 编辑于2016年05月23日 10:57