【Python数据结构】学习笔记二-链表与字符串

2 链表与字符串 2.1 线性表的链接表示

链接表示的特性：
- 不连续的存储单元：不要求逻辑关系相邻的两个元素在物理位置上也相邻存储
- 附加信息：通过增加链接来显示地指示元素之间的逻辑关系和后继元素的位置
基于链接技术实现的线性表称为链接表或链表

2.1.1 单链表

单链表是最简单的链表表示：只为每个数据元素关联一个链接，表示后继关系
每个节点包含两个域
- 数据域：存放元素本身信息
- 链接域：存放后继结点的标识
在单链表中，与表里的 n n n个元素对应的 n n n个节点通过链接形成一条节点链。从表里的任何一个节点都可以找到保存下一元素的节点
一个具体的表由一些具体的结点构成
- 每个节点有自己的标识（常直接称为链接）
- 节点之间通过链接建立起顺序联系
- 给表的最后一个节点（表尾节点）的链接域设置一个不会作为节点对象标识的值（Python中使用None，称为空链接
通过判断是否为空链接，可知道是否已经到达表尾

2.1.2 单链表操作：

基本操作：
- 创建空链表：表头设置为空
- 删除链表：Python中只需要将表链接设为None，Python会自动回收不用的存储
- 判断表是否为空：检查表头是否为None
- 判断表是否满：链表不会满，除非存储空间用完
加入元素：
- 首端加入：
  - 创建新结点存入数据
  - 把原链表的首节点的链接存入新结点的链接域
  - 修改表头变量使其引用新结点
- 尾端加入：
  - 创建一个新结点存入数据
  - 表空时让表头变量引用这个新结点并结束，否则找到表尾节点
  - 令表尾节点的链接域引用这一新结点，并将新节点的链接域设置为空链接
- 定位加入：
  - 找到新节点加入位置的前一节点，不存在时结束
  - 创建新节点存入数据
  - 修改前一节点和新节点的链接域，将节点连入
删除元素：
- 首端删除：直接修改表头链接
- 尾端删除：找到倒数第二个节点，将其链接域设置为空连接
- 定位删除：找到要删除元素所在节点的前一节点，修改它的链接域，将要求删除的节点从表中去除
遍历元素：顺序检查所有元素；求表元素个数；在表中查找特定元素
复杂性：
- 基本操作：
  - 创建空表： O ( 1 ) O(1) O(1)
  - 删除表： O ( 1 ) O(1) O(1)
  - 判断空表： O ( 1 ) O(1) O(1)
- 加入元素：
  - 首端加入： O ( 1 ) O(1) O(1)
  - 尾端加入： O ( n ) O(n) O(n)
  - 定位加入： O ( n ) O(n) O(n)
- 删除元素：
  - 首端删除： O ( 1 ) O(1) O(1)
  - 尾端删除： O ( n ) O(n) O(n)
  - 定位删除： O ( n ) O(n) O(n)
- 需要扫描表的操作： O ( n ) O(n) O(n)
- 需要遍历表的操作： O ( n ) × T O(n)times T O(n)×T

2.1.3 单链表Python语言描述

class LNode:
    def __init__(self, elm, nxt=None):
        self.elem = elm
        self.next = nxt

if __name__ == '__main__':
    llist1 = LNode(1)
    pnode = llist1
    for i in range(2, 11):
        pnode.next = LNode(i)
        pnode = pnode.next
    pnode = llist1
    while pnode is not None:
        print(pnode.elem)
        pnode = pnode.next

运行结果：

1
2
3
4
5
6
7
8
9
10

进程已结束,退出代码0

我们希望基于结点 LNode 定义⼀种链接表类型，为此定义⼀个表类

class LList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def prepend(self, elem):
        self.head = LNode(elem, self.head)

    def append(self, elem):
        if self.head is None:
            self.head = LNode(elem, None)
        p = self.head
        while p.next is not None:
            p = p.next
        p.next = LNode(elem, None)

    def pop(self):  # 首端弹出
        if self.head is None:
            raise ValueError
        e = self.head.elem
        self.head = self.head.next
        return e

    def poplast(self):
        if self.head is None:  # 空链表报错
            raise ValueError
        p = self.head
        if p.next is None:  # 如果链表只有一个元素
            e = p.elem
            self.head = None  # 初始化头结点
            return e  # 返回唯一节点的值
        while p.next.next is not None:  # 直到p.next是最后一个节点
            p = p.next
        e = p.next.elem  # 取出最后一个节点的值
        p.next = None  # p作为最后一个节点
        return e

    def find(self, pred):  # 在表里找到第一个满足pred的元素返回
        p = self.head
        while p is not None:
            if pred(p.elem):
                return p.elem
            p = p.next
        return p.next

    def printall(self):  # 输出表中所有元素
        p = self.head
        while p is not None:
            print(p.elem, end='->')
            p = p.next
        print()

简单使用

mlist1 = LList()
for i in range(10):
    mlist1.prepend(i)
    for i in range(11,20):
        mlist1.append(i)
mlist1.printall()

输出结果

9->8->7->6->5->4->3->2->1->0->11->12->13->14->15->16->17->18->19->
进程已结束,退出代码0

2.1.4 单链表的变形

单链表可以根据需要修改设计：
- 单链表的尾端加入效率低，实际情况中可能需要频繁地在表的两端加入元素

2.1.4.1 带尾节点引用的单链表

如果给表对象增加对表尾的引用，那么尾端加入元素可以做到 O ( 1 ) O(1) O(1)
通过继承方式定义新类LList1

class LList1(LList):
    def __init__(self):
        LList.__init__(self)  # 复用LList的初始化方法
        self.rear = None  # rear指向表尾

    def prepend(self, elem):  # 前端加入
        self.head = LNode(elem, self.head)  # 修改首端节点为修改值，并且链接原来的首端节点
        if self.rear is None:  # 如果是空表
            self.rear = self.head  # 表尾也就是表头

    def append(self, elem):  # 尾端加入
        if self.head is None:   # 如果是空表
            self.prepend(elem)  # 尾端加入也就是首端加入
        else:
            self.rear.next = LNode(elem, None)  # 修改原有尾端节点的链接，指向当前结点
            self.rear = self.rear.next  # 修改保存在表对象中对表尾的引用

    def pop(self):  # 首端弹出
        if self.head is None:  # 如果是空表则报错
            raise ValueError
        # 此时表非空
        e = self.head.elem  # 取值
        if self.rear == self.head:  # 如果表中只有一个元素，表头即表尾
            self.rear = None  # 此时弹出影响到表尾，故修改表尾引用
        self.head = self.head.next  # 头结点更改为原有头结点的后继
        return e

    def poplast(self):  # 尾端弹出
        if self.rear == self.head:  # 如果尾节点引用的是头结点，要么是空表，要么只有一个元素
            # 两种情况下poplast和pop都无差别，于是调用pop
            return self.pop()
        # 此时表非空，有两个或以上的元素
        p = self.head  # 建立从头结点开始的指针，遍历找到尾节点的前一个元素
        while p.next.next is not None:
            p = p.next
        # 此时p是尾节点的前驱，p.next是尾节点，p.next.next是None
        e = p.next.elem  # 取出需要的值
        p.next = None  # 使p为尾节点，和原有尾节点断链
        self.rear = p  # 更改在表中的记录
        return e

测试一下功能

mlist2 = LList1()
import random
origin = list(range(10))
random.shuffle(origin)
for i in origin:
    mlist2.append(i)
mlist2.printall()
mlist2.pop()
mlist2.printall()
mlist2.poplast()
mlist2.printall()

输出结果

4->6->5->1->8->9->0->7->2->3->
6->5->1->8->9->0->7->2->3->
6->5->1->8->9->0->7->2->

进程已结束,退出代码0

2.1.4.2 循环链表

将单链表的最后一个节点的链接设置为指向头节点，这样就得到了循环链表
循环链表从任意节点出发都能访问所有节点
让表头链接指向循环链表尾端节点，可以方便对表头和表尾的操作
循环链表插入第一个元素时需要特别处理
带头结点的循环链表：

2.1.4.3 双链表

单链表找指定节点的前驱比较困难，可以设计双链表来克服此缺点
每个节点都设置前驱链接和后继链接，既可以找到前驱，也可以找到后继

2.2 字符串及其抽象数据类型 2.2.1 字符串的基本概念

字符串，简称串，是一种特殊的线性表，表中的每个元素都是一个字符
一个串可以记为 s = " s 0 s 1 . . . s n − 1 " ( n ≥ 0 ) s="s_0s_1...s_{n-1}"(n≥0) s="s0s1...sn−1"(n≥0)
- s是串的名字
- 字符序列 s 0 s 1 . . . s n − 1 s_0s_1...s_{n-1} s0s1...sn−1是串的值
- 字符个数称为该串的⻓度
⻓度为0的串称为空串，写成s=""，注意与空⽩字符构成的串s= " "相区分

2.2.2 字符串的相等与字典序关系

两个字符串相等：
- 两个字符串的长度相等
- 对应位置上的字符都相同
如果整个字符集上有全（线）序关系，则两个字符串之间有如下字典序关系：
- 设 A = a 0 a 1 . . . a n − 1 A=a_0a_1...a_{n-1} A=a0a1...an−1， B = b 0 b 1 . . . b m − 1 B=b_0b_1...b_{m-1} B=b0b1...bm−1，则 A < B A
- 存在 k k k使得 a i = b i ( i = 0 , 1 , . . . , k − 1 ) a_i=b_i(i=0,1,...,k-1) ai=bi(i=0,1,...,k−1)，但是 a k < b k a_k
- 或者 n < m n

2.2.3 字符串的拼接
串与串的最重要运算是拼接（concatenate），在Python⾥⽤+表示拼接运算
字符串 s 1 = a 0 a 1 … a n − 1 s_1 = a_0a_1…a_{n-1} s1=a0a1…an−1, s 2 = b 0 b 1 … b m − 1 s_2 = b_0b_1… b_{m-1} s2=b0b1…bm−1的拼接为串 s = s 1 + s 2 = a 0 a 1 … a n − 1 b 0 b 1 … b m − 1 s=s_1+s_2=a_0a_1…a_{n-1}b_0b_1… b_{m-1} s=s1+s2=a0a1…an−1b0b1…bm−1
显然s的⻓度为 s 1 s_1 s1与 s 2 s_2 s2的⻓度之和
2.2.4 子串、主串与子串位置

子串与主串：字符串s1中任意个连续的字符组成的⼦序列s2被称为是s1的⼦串，⽽称s1是s2的主串

空串是任意串的⼦串
除s外， s的其他⼦串称为s的真⼦串

⼦串在主串中的位置：该⼦串的第⼀个字符在主串中的位置

A = “PEKINGUNIVERSITY”

0 6

B = “UNIVERSITY”

如果 s1 是 s2 的⼦串， s2 ⾥可能出现多个与 s1相同的段

babb 在 babbabbbbabb ⾥有三个出现，前两个有重叠

特殊子串：

如果存在 s’ 使 s2 = s1 + s’，称 s1 为 s2 的⼀个前缀
如果存在 s 使得 s2 = s + s1，称 s1 为 s2 的⼀个后缀
显然，空串和s既是s的前缀，也是s的后缀

串运算：

n n n次幂： s n s^n sn表示由连续 n n n个 s s s拼接而成的串，在Python中用s*n表示
串替换：指将⼀个串⾥的⼀些（互不重叠的）⼦串代换为另⼀些串得到的结果（由于可能重叠，需规定代换的顺序，如从左到右）

2.2.5 字符串理论
字符串集合和拼接操作构成了⼀种代数结构
空串是拼接操作的“单位元” （⺓元），有结合律，⽆交换律
串集合加上拼接操作，构成⼀个半群（⼀种典型的⾮交换半群）
有单位元，因此是⼀个⺓半群

关于串的理论有许多研究⼯作
基于串和串替换，研究者提出了 post 系统，这是⼀种与图灵机等价的计算模型
（串）重写系统（rewriting system）是计算机理论的⼀个研究领域，⼀直⾮常活跃，有许多重要结果和应⽤，例如现在应⽤⾮常⼴泛的Maude语⾔

2.2.6 抽象数据类型
ADT String: String(self, sseq) # 基于字符序列sseq创建⼀个字符串。 is_empty(self) # 判断本字符串是否为空串。 len(self) # 取得字符串的⻓度。 concat(self, string) # 做出本字符串与另⼀字符串string的拼接串。 substr(self, a, b) # 取得字符串中[a:b] 的⼦串，左闭右开区间。 char(self, index) # 取得字符串中位置index的字符。 match(self, string) # 查找串string在本字符串中第⼀个出现的位置。 subst(self, str1, str2) # 做出将本字符串⾥的⼦串str1都替换为str2的结果串。 end ADT String
2.3 字符串的实现
串是字符的线性序列。可采用线性表，考虑顺序表示和链接表示；也可根据串本身的特点使用其他表示方式。关键问题：表示方式应很好支持串的相关操作。
2.3.1 字符串表示的两个问题

串内容存储

连续存储在一块存储区
一个字符存入一个独立存储块，链接起来

串结束的表示：由于字符串长度不定，需要标记串的结束

用专门数据域记录字符串长度
用一个特殊符号表示串结束（如C语言）

2.3.2 字符串的操作
许多串操作是线性表操作的具体实例，包括串拼接。下⾯考虑⼀个特殊的操作：串替换。
牵涉到三个串：被处理的主串 s，作为被替换对象需要从 s 中替换掉的⼦串 t，以及⽤于代换 t 的 t’
由于 t 可能在 s 中出现多次，因此需要通过⼀系列具体的⼦串代换完成整个替换
由于多次出现可能重叠，只能规定⼀种替换顺序（例如从左到右），⼀次替换破坏的⼦串不应再换⼊新串
⼀次⼦串替换后，应该从换⼊的新串之后继续⼯作。即使换⼊新串之后形成的部分能与 t 匹配，也不应在本次替换中考虑
易⻅：串替换的关键是找到串匹配，这是后⾯讨论的主题

2.3.3 Python中的字符串

Python内部类型str是抽象字符串概念的一个实现

str是不变类型
但不同的str对象长度不同

Python采用一体式连续形式表示str对象

str对象操作分为两类：

获取str对象的信息，如得到串长，检查串内容是否全为数字等
基于str对象构造新的str对象，例如大写/小写拷贝等

2.3.4 字符串操作的实现
检查字符串内容的操作：
① O ( 1 ) O(1) O(1)时间的简单操作：len()和定位访问等
②扫描整个串的操作：in、not in、min、max；字符类型判断

构造新字符串的操作：基本模式都包含两部分
为新构造的串安排一块存储
根据被操作串构造出一个新串

2.4 模式匹配（子串查找） 2.4.1 概念
假设有两个串：

t = t 0 t 1 t 2 . . . t n − 1 t=t_0t_1t_2...t_{n-1} t=t0t1t2...tn−1为目标串（target）
p = p 0 p 1 p 2 . . . p n − 1 p=p_0p_1p_2...p_{n-1} p=p0p1p2...pn−1为模式串（pattern）
通常 m < < n m<

模式匹配就是在目标串 t t t中查找与模式串 p p p相同的子串的过程

如前所述，串匹配是最重要的字符串操作，也是其他许多重要字符串操作的基础。实际中 n 可能⾮常⼤， m 也可以有⼀定规模，也可能需要做许多模式串和/或许多⽬标串的匹配，有关算法的效率⾮常重要

许多计算机应⽤的最基本操作是字符串匹配
⽤编辑器或字处理系统⼯作时，在⽂本中查找单词或句⼦（中⽂字或词语），在程序⾥找拼写错误的标识符等
email 程序的垃圾邮件过滤器， google 等⽹络搜索引擎
各种防病毒软件，主要靠在⽂件⾥检索病毒模式串

分子生物学acgt模式匹配
2.4.2 朴素的模式匹配
将t中的每一位作为可能的开头，与p比较

朴素的模式匹配代码

def nmatching(t, p): # t: target; p:pattern j, i = 0, 0 # j:目标串的起始指针；i：模式串的起始指针；都从头开始 n, m = len(t), len(p) # n:目标串的长度；m:模式串的长度 while j < n and i < m: # 在各自不超过其长度的范围内遍历；如果i=m说明模式串全部匹配成功 if t[j] == p[i]: # 如果当前指针同时匹配 j, i = j + 1, i + 1 # 向后比较一位 else: # 不匹配 j, i = j - i + 1, 0 # 目标串中，指针落在开始匹配时j-i的后一位，模式串回到开头 if i == m: # 匹配成功 return j - i # 返回开始匹配的位置 return -1 # 匹配失败返回-1

简单测试

if __name__ == '__main__': t = "PEKING UNIVERSITY" p = "UNIVERSITY" print(nmatching(t, p))

运行结果

7 进程已结束,退出代码0

算法分析：

最坏的情况下，每趟比较都在最后一位不匹配，则最多比较 n − m + 1 n-m+1 n−m+1趟，总比较次数为 m × ( n − m + 1 ) = O ( m × n ) mtimes(n-m+1)=O(mtimes n) m×(n−m+1)=O(m×n)
例如：t=0000000000000000000000000001, p=001
匹配过程有回溯

算法效率低的原因：把每次字符比较看作完全独立的操作
没有利用字符串本身的特点
没有利用之前已经做过比较的字符的信息

从数学上看，这样做相当于认为⽬标串和模式串⾥的字符都是随机量，⽽且有⽆穷多可能取值，两次字符⽐较相互⽆关也不可借鉴
实际字符串取值来⾃⼀个有穷集合
每个串都有穷。特别是模式串通常不太⻓，⽽且可能反复使⽤

设有t =“ababbabbababa” ；p =“ababa”

① ababbabbababa # 此时完全可以直接跳至第六步

ababa

② ababbabbababa

ababa

③ ababbabbababa

ababa

④ ababbabbababa

ababa

⑤ ababbabbababa

ababa

⑥ ababbabbababa # 此时完全可以直接跳至第九步

ababa

⑦ ababbabbababa

ababa

⑧ ababbabbababa

ababa

⑨ ababbabbababa

ababa

提高匹配速度：

如果在匹配中出现 p i p_i pi与 t j t_j tj不相等
希望能找到一个大于等于1的右移位数，确定 p p p与 t t t继续比较的位置
希望匹配过程对于 t t t是无回溯的
右移若干位后，立即用 p p p中一个新字符 p k p_k pk与 t j ( t j + 1 ) t_j(t_{j+1}) tj(tj+1)继续比较

最好能通过对 p p p的分析得到右移位置 p k p_k pk
2.4.3 KMP算法：无回溯的匹配模式 2.4.3.1 KMP算法的next表
与 p i p_i pi对应 k k k值与被匹配的目标串 t t t无关，通过对模式串 p p p的分析，可以得到每个 i i i对应的 k k k值
假设 p p p的长度为 m m m，现在需要对每一个字符的下标 i i i计算出其相应的 k k k值并保存起来，以便在匹配中使用
把这 m m m个值存入表next，用next[i]表示 i i i对应的 k k k值
当 p i p_i pi匹配失败时，用它之前任何字符与 t j t_j tj比较都无意义，这时应当用 p 0 p_0 p0从头开始与 t j + 1 t_{j+1} tj+1比较；此时令next[i] = -1
显然，对于任何模式串都有next[0] = -1
2.4.3.2 算法思想
假设此时表next已经建立好

匹配中 p i ≠ t j p_ineq t_j pi=tj时，通过next取得应与目标串当前字符匹配模式串里的字符下标
若next[i] >= 0右移i - next[i]个字符，即下一步用 p n e x t [ i ] p_{next[i]} pnext[i]与 t j t_j tj比较
若next[i] = -1，下一步用 p 0 p_0 p0与 t j + 1 t_{j+1} tj+1比较

此时拥有了next表后的代码如下：大致和朴素算算法相同

def matchingKMP(t, p, next): j, i = 0, 0 # 分别对应目标串和模式串的起始指针 n, m = len(t), len(p) # 分别为目标串和模式串的长度 while j < n and i < m: # 在各自长度范围内遍历 if i == -1 or t[j] == p[i]: # 如果i=-1说明模式串要从头开始匹配，此时i=0和i+=1效果相同 j, i = j + 1, i + 1 else: # 当前位置失配 i = next[i] # 从next取出下一次要匹配的字符位置 if i == m: # 此时模式串每一个字符成功 return j - i # 返回起始位置 return -1 # 没有找到
2.4.3.3 next表的构建

next的性质：当匹配中出现失配时， p i ≠ t j p_ineq t_j pi=tj，失配部分前 i − 1 i-1 i−1个字符都是匹配的

因此需要考虑，模式串 p p p的子串 p 0 p 1 . . . p i − 1 p_0p_1...p_{i-1} p0p1...pi−1中相同的前缀和后缀

把与当时后缀相同的前缀移来，前面一段便保证匹配
如果把最大的相同前缀移来，就可保证不遗漏的匹配
若 p 0 … p i − 1 p_0…p_{i-1} p0…pi−1中最⼤的相同前缀与后缀（不包括 p 0 … p i − 1 p_0…p_{i-1} p0…pi−1本身，但允许为空串）的⻓度为。当 $pi ≠ tj 时 , p 就应右移时, p 就应右移时,p就应右移 i - k$ 位, 随后应⽐较$ p_k$ 与 $t_j $．即next[i] = k

此时求解next的问题转化为：对于每一个 i i i，求出 p p p的子串 p 0 . . . p i − 1 p_0...p_{i-1} p0...pi−1中最大相同前缀和后缀的长度

next的计算：递推算法

初始状态：对于任何模式，都有next[0] = -1（在第一个字符之前的子串是空串）

接下来考虑，如果next[0]到next[i]都已经求出，如何计算next[i+1]？

假设next[i] = k，首先判断next[i+1]是否等于k+1

如果 p i = p k p_i=p_k pi=pk，可以得出结果：next[i+1] = k+1。根据上图， p i − k . . . p i − 1 p_{i-k}...p_{i-1} pi−k...pi−1是 p i p_i pi前子串的最大相同后缀； p 0 . . . p k − 1 p_0...p_{k-1} p0...pk−1是最大相同前缀。而 p i + 1 p_{i+1} pi+1前子串就是 p i p_i pi前子串加上 p i p_i pi，此时 p i − k . . . p i − 1 p i p_{i-k}...p_{i-1}p_i pi−k...pi−1pi和 p 0 . . . p k − 1 p k p_0...p_{k-1}p_k p0...pk−1pk分别构成 p i + 1 p_{i+1} pi+1前子串的最大相同后缀和前缀

如果 p i ≠ p k p_ineq p_k pi=pk，那么 p i + 1 p_{i+1} pi+1前子串需要在 p i p_i pi前子串的最大相同前后缀的子串中找，即比较 p n e x t [ k ] p_{next[k]} pnext[k]和 p i p_i pi，检查长度为next[k+1]的前后缀是否相等。已知 p i + 1 p_{i+1} pi+1前子串后缀必然有 p i p_i pi，而 p k ≠ p i p_kneq p_i pk=pi ，只能在 p k p_k pk前子串寻找是否有满足条件的前后缀。

因此得递推算法如下：

①假设next[i] = k，若 p k = p i p_k = p_i pk=pi，则 p i + 1 p_{i+1} pi+1前子串的最大相同前后缀长度为next[i+1] = k+1
②若 p k ≠ p i p_kneq p_i pk=pi，置 k k k为next[k]（考虑更短的前缀匹配），然后转到①
③若 k k k值为-1，说明 p i p_{i} pi前子串最大相同前后缀长度为0，此时next[i+1] = 0

def genNext(p): i, k, m = 0, -1, len(p) # i：遍历起始指针，k：初始k值为0，m是模式串的长度 nxt = [-1] * m # 创建初始next表 while i < m - 1: # 遍历模式串中每一个字符，m-1因为长度要转换成下标范围 while k >= 0 and p[i] != p[k]: # 如果pi != pk，使用递推，寻找比当前更短的相同前后缀 k = nxt[k] # 此时k=-1或者pi=pk，如果k=-1，设置k=0和k+1作用相同；如果pi=pk，说明相同前后缀可以向后延一位 i, k = i + 1, k + 1 nxt[i] = k # 记录当前i值的i前子串最长公共前后缀的长度 return nxt

next的改进：

当 p i ≠ t j p_ineq t_j pi=tj时，如果 p i = p k p_i=p_k pi=pk，则一定有 p k ≠ t j p_kneq t_j pk=tj，所以模式串应当再向右移动k-next[k]位，下一步使用 p n e x t [ k ] p_{next[k]} pnext[k]与 t j t_j tj比较

def genNext_modified(p): i, k, m = 0, -1, len(p) nxt = [-1] * m while i < m - 1: while k >= 0 and p[i] != p[k]: k = nxt[k] # 此时k=-1或者pi=pk i, k = i + 1, k + 1 if p[i] == p[k]: # 如果pi=pk，如果pi与tj失配，pk必然与tj失配 # 还需要寻找更短的相同前后缀，即寻找next[k] nxt[i] = nxt[k] else: nxt[i] = k return nxt

2.4.3.4 算法分析
构建next表：
外层循环每次将i+1，共执行m-1次；k = k+1，执行m-1次
内层循环k = next[k]，最多执行m-1次
时间代价 O ( m ) O(m) O(m)

KMP算法执行不回溯
可以一边读入一遍匹配，不需要回头重读，不需要保存目标串
做好next表后，无回溯匹配需要 O ( n ) O(n) O(n)

如果需要多次使⽤⼀个模式串，相应的next表只需建⽴⼀次（如在⼤⽂件⾥反复找⼀个单词）
这种情况下，可以考虑将 next 表作为模式串的⼀个成分（另外定义⼀个模式串类型）
2.4.3.5 示例
简单测试：

t = "aabcbabcaabcaababc" p = "abcaababc" nxt = genNext_modified(p) print(nxt) print(matchingKMP(t,p,nxt))

运行结果：

[-1, 0, 0, -1, 1, 0, 2, 0, 0] 9 进程已结束,退出代码0

过程：

建立next表

下标 0 1 2 3 4 5 6 7 8
p a b c a a b a b c
k -1 0 0 0 1 1 2 1 2
p k ? = p i p_k?=p_i pk?=pi ≠ neq = ≠ neq = = = = ≠ neq = = = = ≠ neq = = = = = = =
next[i] -1 0 0 -1 1 0 2 0 0

2.5 小结
链接存储结构的优点：
不需要预先分配大量连续空间
线性表的插入和修改只需要修改链接域，而不需要移动其他元素

链接存储结构的缺点：
每个节点中的链接域需要额外占用存储空间，存储密度小
链接存储结构式非随机存储结构，查找任意节点都需要从头开始，增加了算法的时间代价

字符串是由字符作元素组成的线性表，但是作为一种抽象数据类型，拥有其特有的操作
模式匹配时子串在主串中的定位操作，是一个比较常用的操作
朴素的模式匹配比较直观，易于理解，但是效率比较低
无回溯的模式匹配有很强的技巧性，需要依靠next表的支持；计算next的本质还是无回溯的模式匹配算法

下标	0	1	2	3	4	5	6	7	8
p	a	b	c	a	a	b	a	b	c
k	-1	0	0	0	1	1	2	1	2
p k ? = p i p_k?=p_i pk?=pi		≠ neq =	≠ neq =	= = =	≠ neq =	= = =	≠ neq =	= = =	= = =
next[i]	-1	0	0	-1	1	0	2	0	0

【Python数据结构】学习笔记二-链表与字符串

Python相关栏目本月热门文章