串 的 定 义 串 的 逻 辑 结 构 和 基 本 操 作 串 的 存 储 结 构 串 的 实 现 串 的 模 式 匹 配 算 法 进 阶 导 读 本 章 小 结
3.1 串 的 定 义 假 设 V 是 程 序 设 计 语 言 所 采 用 的 字 符 集, 由 字 符 集 V 上 的 字 符 所 组 成 的 任 何 有 限 序 列, 称 为 字 符 串 ( 或 简 称 为 串 ): s= a 1 a 2 a n (n 0) 其 中 : s 是 串 的 名 ; 两 个 双 引 号 之 间 的 字 符 序 列 a 1 a 2 a n 是 串 的 值 ; a i V (1 i n) 是 字 符 集 上 的 字 符 串 中 字 符 的 数 目 n 称 为 串 的 长 度 长 度 为 0 的 串 称 为 空 串 一 个 串 的 子 串 是 这 个 串 中 的 任 一 连 续 子 序 列 包 含 子 串 的 串 相 应 地 称 为 主 串 通 常 称 字 符 在 序 列 中 出 现 的 序 号 为 该 字 符 在 串 中 的 位 置 相 应 地, 子 串 在 主 串 中 的 位 置 则 以 该 子 串 的 第 一 个 字 符 在 主 串 中 的 位 置 来 表 示 2
3.2 串 的 逻 辑 结 构 和 基 本 操 作 在 逻 辑 结 构 方 面, 串 与 线 性 表 极 为 相 似, 区 别 在 于 串 的 数 据 对 象 约 束 为 字 符 集 字 符 串 的 逻 辑 表 示 : 数 据 对 象 :D={a i a i 字 符 集, i=1,2,,n, n 0} 数 据 关 系 :R={<a j-1, a j > (a j-1 D) (a j D), 2 j n} 3
在 基 本 操 作 方 面, 串 与 线 性 表 差 别 很 大 线 性 表 : 大 多 以 单 个 元 素 为 操 作 对 象, 如 : 在 线 性 表 中 查 找 某 个 元 素 在 某 个 位 置 上 插 入 一 个 元 素 或 删 除 一 个 元 素 等 ; 串 : 通 常 以 串 的 整 体 作 为 操 作 对 象, 如 : 在 串 中 查 找 某 个 子 串 在 串 的 某 个 位 置 上 插 入 一 个 子 串 或 删 除 一 个 子 串 等 字 符 串 数 据 结 构 需 支 持 的 基 本 操 作 : 1. Assign 字 符 串 的 初 始 化, 用 字 符 串 常 量 或 字 符 串 类 型 为 当 前 字 符 串 初 始 化 2. GetLen 获 得 字 符 串 的 长 度 3. IsEmpty 判 断 当 前 字 符 串 是 否 为 空 串 4. Empty 清 空 当 前 字 符 串, 即 使 当 前 串 为 空 串 5. Comp 比 较 两 个 字 符 串 是 否 相 等 6. Concat 将 两 个 字 符 串 拼 接 在 一 起 7. SubString 获 得 位 置 pos 开 始, 长 度 为 len 的 子 串 8. Find 获 得 字 符 串 中 子 串 的 出 现 位 置 除 上 述 基 本 操 作 外, 字 符 串 上 的 操 作 还 包 括 Insert Delete Replace 等 相 对 串 上 的 基 本 操 作, 这 些 操 作 相 对 比 较 复 杂 4
3.3 串 的 存 储 结 构 1. 数 组 存 储 2. 块 链 存 储 5
3.3.1 串 的 数 组 存 储 表 示 (1) 静 态 数 组 存 储 方 法 为 字 符 串 变 量 分 配 一 个 固 定 长 度 的 存 储 空 间 一 般 用 定 长 数 组 加 以 实 现 const int nmaxlen=1024; // 字 符 串 的 最 大 长 度 class SString { private: int nlen; // 字 符 串 的 当 前 长 度 char ch[nmaxlen+1]; // 字 符 串 存 储 空 间 }; 6
(2) 动 态 数 组 存 储 方 法 使 用 C++ 提 供 的 new 操 作 符 分 配 一 块 连 续 的 堆 空 间 class Dstring { private: int nlen; // 字 符 串 长 度 char *ch; // 指 向 当 前 字 符 串 的 指 针 }; 7
3.3.2 串 的 块 链 存 储 表 示 Head F u d a n U n i v e r s i t y # # # # (a) 结 点 大 小 为 5 Head F u d a n... i t y (b) 结 点 大 小 为 1 图 3-1 字 符 串 Fudan University 的 块 链 存 储 方 式 结 点 大 小 的 选 择 和 子 串 存 储 方 式 是 影 响 效 率 的 重 要 因 素 存 储 密 度 串 值 所 占 的 存 储 位 实 际 分 配 的 存 储 位 8
块 链 式 存 储 结 构 对 字 符 串 的 连 接 等 操 作 的 实 现 比 较 方 便, 但 总 体 来 说 操 作 复 杂, 占 用 的 存 储 空 间 大 块 链 存 储 结 构 字 符 串 的 操 作 实 现, 与 线 性 表 的 链 表 实 现 类 似 9
3.4 串 的 实 现 程 序 3-1 提 供 了 字 符 串 的 类 定 义, 封 装 了 3.2 小 节 描 述 的 8 个 基 本 操 作 1. 程 序 3-1 字 符 串 的 类 定 义 #ifndef DSTRING INCLUDED_ 2. #define DSTRING INCLUDED_ 3. 4. const int ninitlen=1024; // 初 始 最 大 长 度 class DString{ 5. public: 6. 7. // 构 造 函 数 : 为 数 组 分 配 ninitlen+1 大 小 的 空 间 ; 初 始 化 串 为 空 串 ; 长 度 为 0 DString( ); // 析 构 函 数 : 释 放 字 符 串 所 占 的 内 存 8. ~DString( ); // 重 载 构 造 函 数 : 用 已 知 的 字 符 串 初 始 化 当 前 字 符 串 9. 10. DString(const DString &strsrc); // 重 载 构 造 函 数 : 用 chsrc 初 始 化 当 前 字 符 串 DString(const char *chsrc); // 内 联 函 数 : 计 算 字 符 串 的 长 度 11. int GetLen( ) const { return nlen; } // 内 联 函 数 : 判 断 当 前 字 符 串 是 否 为 空 串 12. 13. int IsEmpty( ) { return nlen?0:1; } // 内 联 函 数 : 清 空 当 前 字 符 串 void Empty( ) { nlen=0; ch[0]= 0 ; } 14. // 获 得 当 前 字 符 串 位 置 npos 开 始 的 长 度 为 ncount 的 子 串 15. DString GetSub(int npos, intncount)const; // 操 作 符 重 载 : 获 得 指 定 下 标 的 字 符 16. char operator [ ] (int npos)const; // 操 作 符 重 载 : 字 符 串 赋 值 17. Dstring & operator = (const DString &str); // 操 作 符 重 载 : 字 符 串 合 并 18. Dstring & operator += (const DString &str); // 操 作 符 重 载 : 字 符 串 等 值 判 断 19. int operator == (const DString &str) const; // 字 符 串 的 模 式 匹 配 : 精 确 匹 配 20. 21. int Find(DString &strsub) const; // 找 子 串 private: 22. int nlen; // 字 符 串 实 际 长 度 23. char *ch; // 字 符 串 存 储 所 在 的 数 组 24. }; 25. #endif //#define DSTRING INCLUDED_ 10
程 序 3-2 字 符 串 类 的 实 现 1. DString::DString( ){ 2. // 为 动 态 数 组 ch 开 辟 ninitlen+1 的 存 储 空 间 3. ch=new char[ninitlen+1]; 4. if (!ch) { cerr<< Allocate Error!\n ; return; } 5. // 初 始 化 当 前 字 符 串 : 长 度 为 0, 空 串 6. nlen=0; 7. ch[0]= \0 ; 8. } 9. 10. DString::~DString( ) { 11. // 释 放 动 态 数 组 的 存 储 空 间 12. delete [ ] ch; 13. } 14. 11
1. DString::DString(const DString &strsrc) { 2. nlen=strsrc.getlen( ); // 设 置 字 符 串 长 度 3. // 为 动 态 数 组 开 辟 max(strsrc.nlen, ninitlen)+1 的 存 储 空 间 4. if (nlen>ninitlen) 5. ch=new char[nlen+1]; 6. else 7. ch=new char[ninitlen+1]; 8. if (!ch) { cerr<< Allocate Error!\n ; return; } 9. strcpy(ch,strsrc.ch); // 复 制 字 符 串 序 列 10. } 11. DString::DString(const char *chsrc) { 12. nlen=strlen(chsrc); // 设 置 字 符 串 长 度 13. // 为 动 态 数 组 开 辟 max(strlen(chsrc), ninitlen)+1 的 存 储 空 间 14. if (nlen>ninitlen) 15. ch=new char[nlen+1]; 16. else 17. ch=new char[ninitlen+1]; 18. if (!ch) {cerr<< Allocate Error!\n ; return; } 19. strcpy(ch,chsrc); // 复 制 字 符 串 序 列 20. } 12
提 取 子 串 的 算 法 示 例 npos=2, ncount=3 npos=5, ncount=4 i n f i n i t y i n f i n i t y 超 出 f i n npos+ncount-1 nlen-1 i t y npos+ncount-1 nlen 13
1. 2. // 获 取 子 串 DString DString::GetSub(int npos, int ncount)const { 3. DString tmpstring; 4. // 定 义 临 时 字 符 串, 作 为 保 存 子 串 的 临 时 对 象 5. char *pch; // 字 符 串 指 针, 指 向 要 获 取 的 子 串 6. 7. // 判 断 函 数 的 输 入 参 数 是 否 符 合 逻 辑 : // 给 定 子 串 的 在 当 前 串 中 的 位 置 不 能 小 于 0, 8. 9. // 且 子 串 长 度 不 能 小 于 0, 且 子 串 的 不 能 超 出 当 前 串 的 右 边 界 if (npos<0 ncount<0 npos+ncount-1>=ninitlen) { 10. 11. } tmpstring.nlen=0; tmpstring.ch[0]= \0 ; 12. 13. else{ // 将 子 串 拷 贝 到 tmpstring 对 象 中 if (npos+ncount-1<nlen) ncount=nlen-npos; 14. 15. tmpstring.nlen=ncount; pch=ch+npos; 16. memcpy(tmpstring.ch, pch,ncount); 17. tmpstring.ch[ncount]= \0 ; 18. } 19. return tmpstring; // 返 回 获 取 到 的 子 串 20. // 若 函 数 的 参 数 不 合 逻 辑, 返 回 的 是 空 串 21. } 14
1. // 串 赋 值 2. Dstring & DString::operator = (const DString &str) { 3. if (&str!=this) { 4. // 删 除 当 前 动 态 数 组, 并 根 据 str 的 长 度 为 当 前 串 开 辟 存 储 空 间 5. delete [ ]ch; // 释 放 原 有 的 字 符 串 存 储 空 间 6. nlen=str.nlen; // 复 制 字 符 串 的 长 度 7. if (nlen>ninitlen) // 如 果 新 的 长 度 大 于 默 认 的 初 始 化 长 度 8. // 按 新 长 度 申 请 存 储 空 间 9. ch=new char[nlen+1]; 10. else // 否 则, 按 默 认 长 度 申 请 存 储 空 间 11. ch=new char[ninitlen+1]; 12. // 若 申 请 空 间 不 成 功, 则 提 示 错 误 信 息, 并 返 回 空 指 针 13. if (!ch) { cerr<< Allocate Error!\n ; return 0;} 14. // 复 制 字 符 串 序 列 15. strcpy(ch,str.ch); 16. } 17. return *this; 18. } 15
1. Dstring & DString::operator += (const DString &str) { 2. // 当 前 串 与 串 str 拼 接, 拼 接 的 结 果 写 入 当 前 串 3. char *temp=ch; 4. int n=nlen+str.nlen; 5. int m=(ninitlen>=n)? ninitlen:n; 6. // 申 请 新 的 存 储 空 间, 并 进 行 字 符 串 拼 接 7. ch=new char[m+1]; 8. if (!ch) { cerr<< Allocate Error!\n ; return 0; } 9. nlen=n; 10. strcpy(ch,temp); 11. strcat(ch,str.ch); 12. delete [ ]temp; 13. return *this; 14. } 16
1. int DString::operator == (const DString &str) const { 2. // 字 符 串 等 值 判 断 : 相 等 则 返 回 0 3. return strcmp(ch,str.ch); 4. } 5. 6. int DString::Find(DString &strsub) const { 7. // 字 符 串 精 确 匹 配 :Brute-Force 方 法 8. int n=getlen(); 9. int m=strsub.getlen(); 10. for (int j=0; j<=n-m;++j){ 11. for (int i=0; i<m && strsub[i]==ch[i+j]; ++i); 12. if (i>=m) 13. return j; 14. } 15. return -1; 16. } 17
1. char DString::operator [ ] (int npos) const { 2. // 获 取 当 前 串 的 第 i 个 字 符 3. if (npos<0 && npos>=nlen) 4. { cerr<< npos Out Of Bounds! <<endl; return 0;} 5. return ch[npos]; 6. } 18
3.5 串 的 模 式 匹 配 算 法 串 的 模 式 匹 配 算 法 解 决 的 是 在 长 串 中 查 找 短 串 的 一 个 多 个 或 所 有 出 现 的 问 题 通 常, 我 们 称 长 串 为 text, 称 短 串 为 pattern 一 个 长 度 为 m 的 pattern 可 被 表 述 为 x=x[0..m-1]; 长 度 为 n 的 text 可 被 表 述 为 y=y[0..n-1]; 而 模 式 匹 配 的 任 务 是 找 到 x 在 y 中 的 出 现 模 式 匹 配 过 程 中, 程 序 会 查 看 text 中 长 度 为 m 的 窗 口, 即 用 pattern 串 和 text 的 窗 口 中 的 子 串 进 行 比 对 比 对 完 成 后, 将 窗 口 向 右 滑 动, 并 不 断 重 复 这 一 过 程 直 到 根 据 需 要 找 到 所 需 匹 配 为 止 这 种 机 制 被 称 为 滑 动 窗 口 机 制 本 节 所 讨 论 的 若 干 串 模 式 匹 配 算 法 都 是 基 于 滑 动 窗 口 机 制 的 算 法 19
定 义 在 串 中 寻 找 子 串 ( 第 一 个 字 符 ) 在 串 中 的 位 置 词 汇 在 模 式 匹 配 中, 子 串 称 为 模 式, 串 称 为 目 标 示 例 目 标 T : Beijing 模 式 P : jin 匹 配 结 果 = 3 20
模 式 匹 配 的 哲 理 词 汇 目 标 : 外 面 的 世 界 模 式 : 小 小 的 我 定 义 在 外 面 的 世 界 中 寻 找 小 小 的 我 的 位 置 21
BF(Brute-Force) 算 法 BF 算 法 是 最 基 本 的 串 模 式 匹 配 算 法 程 序 3-2 的 Find 函 数 就 是 利 用 BF 算 法 实 现 的 查 找 最 左 匹 配 的 实 现 其 过 程 是 : 依 次 比 对 pattern 和 滑 动 窗 口 中 的 对 应 位 置 上 的 字 符 ; 比 对 完 成 后 将 滑 动 窗 口 向 右 移 动 1, 直 到 找 到 所 需 的 匹 配 为 止 22
第 一 轮 比 较 : y C G T A G C G T C T C T C A T A T G T C A T G C 1 2 3 4 x C G T C T C T C 比 较 窗 口 右 移 1 个 位 置 第 二 轮 比 较 : y C G T A G C G T C T C T C A T A T G T C A T G C 1 x C G T C T C T C 比 较 窗 口 右 移 1 个 位 置 第 三 轮 比 较 : y C G T A G C G T C T C T C A T A T G T C A T G C 1 x C G T C T C T C 比 较 窗 口 右 移 1 个 位 置... 第 六 轮 比 较 : y C G T A G C G T C T C T C A T A T G T C A T G C 1 2 3 4 5 6 7 8 x C G T C T C T C 找 到 子 串, 程 序 结 束 Brute-Force 算 法 示 例 ( 图 3-2) 23
穷 举 的 模 式 匹 配 算 法 分 析 ( 时 间 代 价 ) 设 模 式 串 P 有 m 个 字 符, 而 目 标 串 T 有 n 个 字 符 : 最 好 情 况 T 的 前 m 个 字 符 与 P 匹 配, 可 在 m 次 比 较 后 找 到 匹 配 结 果, 算 法 复 杂 度 为 O(m) 最 坏 情 况 假 设 未 进 行 比 较 最 后 一 个 字 符 之 类 的 优 化, 且 第 一 个 字 符 总 是 能 匹 配 上, 但 却 永 远 没 有 匹 配 上 的 模 式 如 :P= abc, T= aaaaaaaa (m=3, n=8), 则 模 式 P= abc 的 m (m=3) 个 字 符 必 须 与 T 中 的 文 本 块 一 共 比 较 n-m+1 次, 一 般 情 况 下 必 须 比 较 m 个 字 符 共 (n-m+1) 次, 即 一 共 进 行 m(n-m+1) 次 而 m(n-m+1) <= m(n-m+m)=mn 算 法 复 杂 度 的 估 计 值 为 O(mn) 算 法 速 度 慢 的 原 因 在 于 回 溯 每 趟 重 新 比 较 时, 目 标 串 的 检 测 指 针 要 回 退 24
BF 算 法 的 特 点 总 结 (1) 不 需 要 预 处 理 过 程 ; (2) 只 需 固 定 的 存 储 空 间 ; (3) 滑 动 窗 口 的 移 动 每 次 都 为 1; (4) 字 符 串 的 比 对 可 按 任 意 顺 序 进 行 ( 从 左 到 右 从 右 到 左 或 特 定 顺 序 均 可 ); (5) 算 法 的 时 间 复 杂 性 为 O(m n); (6) 最 大 比 较 次 数 为 (n-m+1) m 25
KR(Karp-Rabin) 算 法 作 为 最 朴 素 的 字 符 串 匹 配 算 法,BF 算 法 的 效 率 并 不 理 想 其 主 要 原 因 有 二 : 其 一 是 子 串 与 滑 动 窗 口 内 的 子 串 逐 个 字 符 匹 配 所 引 发 的 效 率 问 题 ; 其 二 是 该 算 法 太 健 忘, 前 一 次 匹 配 的 信 息 其 实 可 以 有 部 分 可 以 应 用 到 后 一 次 匹 配 中 的, 而 BF 算 法 只 是 简 单 的 把 这 个 信 息 扔 掉, 重 头 再 来 KR 算 法 优 化 滑 动 窗 口 内 容 逐 一 匹 配 KR 算 法 : 将 滑 动 窗 口 内 m 个 字 符 的 比 较 变 为 一 个 哈 希 值 的 比 较 通 过 对 字 符 串 进 行 哈 希 运 算, 然 后 比 较 子 串 哈 希 值 与 滑 动 窗 口 内 子 串 的 哈 希 值 ; 仅 当 这 两 个 哈 希 值 相 等 时, 再 来 比 较 窗 口 内 的 子 串 是 否 相 等 26
程 序 3-3 Karp-Rabin 算 法 框 架 1. function RabinKarp(string s[0..n-1], string sub[0..m-1]) 2. hsub=hash(sub[0..m-1]); // 计 算 子 串 的 哈 希 值 3. hs=hash(s[0..m-1]); // 计 算 窗 口 内 子 串 的 哈 希 值 4. for i from 0 to n-m 5. // 依 次 比 较 窗 口 内 子 串 与 给 定 子 串 是 否 相 同 6. if hs=hsub 7. if s[i..i+m-1]=sub 8. return i; // 如 果 相 同 则 记 录 位 置 并 退 出 函 数 9. hs=hash(s[i+1..i+m]); // 否 则, 当 前 窗 口 右 移 10. return not found; 11. // 没 有 发 现, 记 录 没 有 发 现 给 定 子 串, 退 出 27
哈 希 算 法 KR 算 法 的 效 率 取 决 于 哈 希 函 数 的 的 选 取 通 常,KR 算 法 使 用 h(x)=x mod q 作 为 哈 希 函 数 滑 动 窗 口 的 哈 希 值 计 算 公 式 : hash(w[0..m-1])= (w[0] 2 m-1 + w[1] 2 m-2 + + w[m-1] 2 0 ) mod q 其 中,q 为 一 个 大 整 数 当 滑 动 窗 口 右 移 时, 需 要 对 当 前 窗 口 内 的 子 串 重 新 利 用 哈 希 函 数 计 算, 其 计 算 公 式 为 : rehash(a,b,h)=((h-a 2 m-1 ) 2+b)mod q 其 中,h 为 上 一 滑 动 窗 口 的 哈 希 值 ;a 为 即 将 移 出 滑 动 窗 口 的 字 符 ;b 是 即 将 移 入 滑 动 窗 口 的 字 符 28
程 序 3-4 Karp-Rabin 算 法 ( 窗 口 长 度 为 m,q 选 取 2 m-1 ) 1. #define Rehash(a, b, h) ((((h)-(a)*d)<<1)+(b)) 2. int KR(char *x,intm, char*y,intn){ 3. int d, hx, hy, i, j; 4. // 预 处 理, 计 算 d=2^(m-1), 这 里 的 d 为 算 法 描 述 中 的 q 5. for (d=i=1; i<m; i++) 6. d=d<<1; 7. // 分 别 计 算 字 符 串 x 和 y 的 哈 希 值 8. for (hy=hx=i=0; i<m; i++) { 9. hx=(hx<<1)+x[i]; 10. hy=(hy<<1)+y[i]; 11. } 12. // 查 找 过 程 13. for (j=0; j<=n-m; j++) { 14. // 如 果 哈 希 值 相 等, 再 判 断 字 符 串 是 否 相 等 15. if (hx==hy && memcmp(x, y+j, m)==0) 16. return j; // 如 字 符 串 相 等, 返 回 位 置 17. hy=rehash(y[j], y[j+m], hy); 18. // 否 则, 对 y 上 的 子 串 重 新 进 行 哈 希 19. } 20. return -1; 21. } 29
第 一 轮 比 较 : y C G T A G C G T C T C T C A T A T G T C A T G C x C G T C T C T C Hash(y[0..7])=17910 第 二 轮 比 较 : y C G T A G C G T C T C T C A T A T G T C A T G C x C G T C T C T C Hash(y[1..8])=18735 第 三 轮 比 较 : y C G T A G C G T C T C T C A T A T G T C A T G C x C G T C T C T C Hash(y[2..9])=19378... 第 六 轮 比 较 : y C G T A G C G T C T C T C A T A T G T C A T G C 1 2 3 4 5 6 7 8 x C G T C T C T C Hash(y[5..12])=Hash(x)=18055 找 到 子 串, 函 数 结 束 图 3-3 Karp-Rabin 算 法 示 例 30
KR 算 法 的 特 点 (1) 利 用 哈 希 的 方 法 ; (2) 预 处 理 需 要 O(m) 的 时 间 和 常 数 的 存 储 空 间 ; (3) 最 坏 情 况 下, 算 法 时 间 复 杂 性 为 O(m n); (4) 算 法 时 间 复 杂 性 的 预 期 为 O(m+n) 31
KMP (Knuth-Morris-Pratt) 算 法 BF 和 KR 算 法 的 一 个 共 同 点 是 每 次 比 较 的 窗 口 向 右 滑 动 的 距 离 均 为 1 KMP 算 法, 旨 在 利 用 pattern 的 内 容 指 导 滑 动 窗 口 向 右 滑 动 的 距 离 k 32
KMP (Knuth-Morris-Pratt) 算 法 Knuth-Morris-Pratt (KMP) 算 法 发 现 每 个 字 符 对 应 的 该 k 值 仅 依 赖 于 模 式 P 本 身, 与 目 标 对 象 T 无 关 1970 年,S. A. Cook 在 进 行 抽 象 机 的 理 论 研 究 时 证 明 了 在 最 差 情 况 下 模 式 匹 配 可 在 N+M 时 间 内 完 成 此 后,D. E. Knuth 和 V. R. Pratt 以 此 理 论 为 基 础, 构 造 了 一 种 方 法 来 在 N+M 时 间 内 进 行 模 式 匹 配, 与 此 同 时,J. H. Morris 在 开 发 文 本 编 辑 器 时 为 了 避 免 在 检 索 文 本 时 的 回 溯 也 得 到 了 同 样 的 算 法 33
KMP 算 法 思 想 T T 0 T 1 T i-j-1 T i-j T i-j+1 T i-j+2 T i-2 T i-1 T i T n-1 ǁ ǁ ǁ ǁ ǁ P p 0 p 1 p 2 p j-2 p j-1 p j 则 有 T i-j T i-j+1 T i-j+2 T i-1 = p 0 p 1 p 2 p j-1 (1) 如 果 p 0 p 1 p j-2 p 1 p 2 p j-1 (2) 则 立 刻 可 以 断 定 p 0 p 1 p j-2 T i-j+1 T i-j+2 T i-1 ( 朴 素 匹 配 的 ) 下 一 趟 一 定 不 匹 配, 可 以 跳 过 去, 也 即 模 式 右 移 一 位 后 依 然 不 匹 配
KMP 算 法 思 想 同 样, 若 p 0 p 1 p j-3 p 2 p 3 p j-1 则 模 式 右 移 2 位 也 不 匹 配, 因 为 有 p 0 p 1 p j-3 T i-j+2 T i-j+3 T i-1 直 到 对 于 某 一 个 k 值, 使 得 p 0 p 1 p k p j-k-1 p j-k p j-1 且 p 0 p 1 p k-1 = p j-k p j-k+1 p j-1 则 p 0 p 1 p k-1 = T i-k T i-k+1 T i-1 T i ǁ ǁ ǁ p j-k p j-k+1 p j-1 p j ǁ ǁ ǁ p 0 p 1 p k-1 p k 模 式 右 移 j-k 位
KMP 算 法 的 关 键 : 模 式 本 身 模 式 右 移 j-k 位 T i-j T i-j+1 T i-j+2 T i-k T i-k+1 T i-1 T i ǁ ǁ ǁ ǁ ǁ ǁ p 0 p 1 p 2 p j-k p j-k+1 p j-1 p j ǁ ǁ ǁ 特 征 向 量 p 0 p 1 p k-1 p k 关 键 : 对 每 个 p j, 如 何 求 k 值??
字 符 串 特 征 向 量 设 模 式 P 由 m 个 字 符 组 成, 记 为 P = p 0 p 1 p 2 p 3 p m-1 令 特 征 向 量 N 用 来 表 示 模 板 P 的 字 符 分 布 特 征, 简 称 N 向 量 和 P 同 长, 由 m 个 特 征 数 n 0 n m-1 整 数 组 成, 记 为 N = n 0 n 1 n 2 n 3 n m-1 N 在 大 多 数 文 献 中 称 为 next 数 组, 每 个 n j 对 应 next 数 组 中 的 元 素 next[j]
字 符 串 的 特 征 向 量 模 式 P 的 前 缀 子 串 ( 首 串 ) P 的 前 t 个 字 符 : p 0 p 1 p 2 p t-1 模 式 P 的 左 子 串 ( 尾 串 ) 在 P 的 第 j 位 置 之 前 的 t 个 字 符, 称 为 j 位 置 的 左 子 串 : p j-t... p j-2 p j-1 模 式 P 第 j 个 位 置 的 特 征 数 n j 最 长 的 (t 最 大 的 ) 能 够 与 前 缀 子 串 匹 配 的 左 子 串 ( 简 称 第 j 位 的 最 长 前 缀 串 ) t 即 p j 的 特 征 数 n j
Knuth 等 人 认 为 合 理 的 右 移 方 案 是 根 据 P[0..j-1] 的 最 大 前 缀 和 最 大 后 缀 能 够 匹 配 的 内 容 来 决 定 窗 口 右 移 的 距 离 为 此 KMP 算 设 计 一 个 next 函 数 : next 1 如 果 0 max 0.. 1.. 1 如 果 0.. 1.. 1 && 0 其 他 情 况
对 应 的 求 特 征 向 量 算 法 框 架 在 KMP 快 速 模 式 匹 配 中, 若 用 ni 表 示 第 i 位 的 特 征 值, 特 征 数 n i+1 ( -1 n i < i ) 可 以 采 用 如 下 定 义 : 1. n 0 = -1; 对 于 i> 0 的 n i+1, 假 定 已 知 前 一 位 置 没 有 优 化 以 前 的 特 征 数 n i = k; 2. 当 k > =0, 且 P i P k 时, 则 令 k = n k, 并 让 步 骤 2 循 环 直 到 条 件 不 满 足 ( 变 为 P i = =P k, 或 上 一 步 骤 k == 0 而 导 致 k = n k 步 骤 后 k == -1 了 ); 3. n i+1 = k+1( 这 是 没 有 优 化 以 前 的 特 征 数, 在 优 化 前 传 到 第 一 步 用 于 计 算 下 一 个 特 征 值 );
计 算 next 数 组 1. 求 p 0, p 1,,p j-1 中 最 大 相 同 的 前 缀 与 后 缀 的 长 度 t 2. next[j] = t 计 算 next[j] 时 充 分 利 用 了 位 置 j 之 前 的 各 个 字 符 的 next 值
KMP 算 法 // 不 带 优 化 // 预 处 理 : 计 算 Next 数 组 1. void preprocessing(char *p, int m, int Next[]){ 2. for (int i=0,j=next[0]=-1;i<m-1;){ 3. if (j==-1 p[i]==p[j]){ 4. i++; j++; 5. Next[i]=j; 6. } 7. else 8. j=next[j]; 9. } 1. int KMP(char *p, int m, char *t, int n) 2. { 3. int i, j, Next[SIZE]; 4. // 预 处 理 5. preprocessing(p,m, Next); 6. // 查 找 7. for (i=j=0;j<n;){ 8. if (i==-1 p[i]==t[j]) 9. { i++; j++; } 10. else 11. i = Next[i]; 12. if (i>=m) 13. return j-i; 14. } 15. return -1; 16. }
KMP 模 式 匹 配 : 示 例 a b a c a a b a c c a b a c a b a a 1 2 3 4 5 6 a b a c a b 7 a b a c a b j P j N j 0 a -1 1 b 0 2 a 0 3 c 1 4 a 0 5 b 1 8 9 10 11 12 a b a c a b 13 a b a c a b 14 15 16 17 18 19 a b a c a b
KMP 模 式 匹 配 : 示 例 优 化 的 next[] a b a c a a b a c c a b a c a b a a 1 2 3 4 5 6 a b a c a b 7 8 9 1011 a b a c a b 121314151617 a b a c a b j 0 1 2 3 4 5 P j a b a c a b N j -1 0-1 1-1 0
优 化 后 的 求 特 征 向 量 算 法 框 架 一 般 把 模 式 的 第 一 个 字 符 的 特 征 数 设 置 为 -1, 以 尽 可 能 地 减 少 冗 余 比 较 : 在 KMP 快 速 模 式 匹 配 中, 若 用 ni 表 示 第 i 位 的 特 征 值, 特 征 数 n i+1 ( -1 n i < i ) 可 以 采 用 如 下 定 义 : 1. n 0 = -1; 对 于 i> 0 的 n i+1, 假 定 已 知 前 一 位 置 没 有 优 化 以 前 的 特 征 数 n i = k; 2. 当 k > =0, 且 P i P k 时, 则 令 k = n k, 并 让 步 骤 2 循 环 直 到 条 件 不 满 足 ( 变 为 P i = =P k, 或 上 一 步 骤 k == 0 而 导 致 k = n k 步 骤 后 k == -1 了 ); 3. n i+1 = k+1( 这 是 没 有 优 化 以 前 的 特 征 数, 在 优 化 前 传 到 第 一 步 用 于 计 算 下 一 个 特 征 值 ); 4. 若 P i+1 = =P k+1, 则 n i+1 = n k+1 ( 此 步 骤 为 优 化 )
程 序 3-5 KMP 算 法 // 带 优 化 1. // 预 处 理 : 计 算 Next 数 组 2. void preprocessing(char *p, int m, int Next[]){ 3. for (int i=0,j=next[0]=-1;i<m-1;){ 4. for (;j>-1&&p[i]!=p[j];) 5. j=next[j]; 6. i++; j++; 7. if (p[i] == p[j]) 8. Next[i]= Next[j]; 9. else 10. Next[i]=j; 11. } 12. } 1. int KMP(char *p, int m, char *t, int n) 2. { 3. int i, j, Next[SIZE]; 4. // 预 处 理 5. preprocessing(p,m, Next); 6. // 查 找 7. for (i=j=0;j<n;){ 8. for (;i>-1&&p[i]!=t[j];) 9. i = Next[i]; 10. i++; j++; 11. if (i>=m) 12. return j-i; 13. } 14. return -1; 15. }
程 序 3-5 KMP 算 法 // 带 优 化 1. // 预 处 理 : 计 算 Next 数 组 2. void preprocessing(char *p, int m, int Next[]){ 3. for (int i=0,j=next[0]=-1;i<m-1;){ 4. for (;j>-1&&p[i]!=p[j];) 5. j=next[j]; 6. i++; j++; 7. if (p[i] == p[j]) 8. Next[i]= Next[j]; 9. else 10. Next[i]=j; 11. } 12. } i 0 1 2 3 4 5 P j a b a c a b N j -1 0 0 1 0 1 i 0 1 2 3 4 5 P j a b a c a b N j -1 0-1 1-1 0
预 处 理 过 程 i x[i] Next[i] 0 1 2 3 4 5 6 7 8 C G T C T C T C -1 0 0-1 1-1 1-1 1 查 找 过 程 第 一 轮 : y C G T A G C G T C T C T C A T A T G T C A T G C 1 2 3 4 x C G T C T C T C 窗 口 右 移 4(i-Next[i]=3-(-1)) 第 二 轮 : y C G T A G C G T C T C T C A T A T G T C A T G C 1 x C G T C T C T C 窗 口 右 移 1(i-Next[i]=0-(-1)) 第 三 轮 : y C G T A G C G T C T C T C A T A T G T C A T G C 1 2 3 4 5 6 7 8 x C G T C T C T C 找 到 子 串, 程 序 结 束 图 3-4 KMP 算 法 示 例
KMP 算 法 的 特 点 (1) 与 BF 算 法 类 似, 按 照 从 左 到 右 的 顺 序 进 行 比 较 ; (2) 预 处 理 需 要 O(m) 的 时 间 和 存 储 空 间 ; (3) 算 法 时 间 复 杂 性 为 O(m+n); (4) 查 找 阶 段 的 最 大 比 较 次 数 为 2n-1 49
BM(Boyer-Moore) 算 法 ( 不 要 求 )
3.6 进 阶 导 读 在 C++ 的 STL 库 中 对 字 符 串 进 行 了 封 装 [1], 微 软 的 ATL/MFC 中 将 其 封 装 为 CStringT/CString [2] 最 近, 英 特 尔 在 其 最 新 的 CPU 中 增 加 了 字 符 串 处 理 的 硬 件, 以 加 速 字 符 串 处 理 的 效 率 [3] 字 符 串 匹 配 算 法 可 分 为 两 类 : 精 确 匹 配 和 近 似 匹 配 本 章 所 介 绍 的 模 式 匹 配 算 法 属 于 精 确 匹 配 51
习 题 见 助 教 在 elearning 上 的 通 知 补 1: 试 证 明 KMP 的 算 法 复 杂 度