有哪些信誉好的足球投注网站- 1、本文档共49页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
数据结构PPT教学课件-第4章 串
第4章 串 4.2串的存储结构 4.3 串的运算 4.4 文本编辑 在最坏的情况下, 算法4.4程序运行过程的字符比较总次数为m(nm+1)。 如果用次数来衡量算法的运行时间, 那么算法4.4的运行时间为О(m(nm))。若nm, 则运行时间为О(mn)。 一般说来, 在执行简单匹配算法的字符比较过程中, 一旦出现p［j］≠t［i］(1≤i≤n,1≤j≤m)时, 即 t［1］t［2］ … t［I-j+1］ t［I-j+2］ … t［I-1］ t［i］ … ‖ ‖ ‖ ≠ p［1］ p［2］ … p［j1］ p［j］ … (4.1) 那么, 一定要从模式p的第一个字符开始与正文t中第ij+2个字符开始依次进行比较, 即 p［1］ p［2］ … p［j-k+1］ p［j-k+2］ … p［j-1］ p［j］ p［j+1］ ‖ … ‖ ‖ ? p［1］ … p［2］ p［j2］ p［k］ p［k+1］… 那么, 由式(4.1)和式(4.2)可得 t［1］ t［2］ … t［I-j-1］ … t［I-k+1］ … t［I-1］ t［i］ t［i+1］ … ‖ ‖ ‖ ≠ p［1］ … p［I-k+1］ … p［j-1］ p［j］p［j+1］ ‖ ‖ ? p［1］ … p［k1］ p［k］[p-k+1］ 因此, 只要从模式p中的p［k］开始, 与正文t中的t［i］开始依次继续进行比较, 就可以减去前面的k1次比较。 如果满足式(4.2)的k有多个, 那么一定要取最大的k, 否则可能会错过匹配成功的机会。 例如, 对于 t: aaaabcde p: aaabc 在执行匹配时出现了如下的状态: t: a a a a b c d e ‖ ‖ ‖ ≠ a a a b 因p［4］≠t［4］, 此时满足式(4.2), k可取1,2,3。 如果取k=1, 那么在执行下面的匹配时, 将出现如下的比较序列: t: a a a a b c d e ‖ ≠ p: a a a b c 这时将错过匹配成功的机会。 如果取k=2, 那么在执行下面的匹配时, 将出现如下的比较序列: t: a a a a b c d e ‖‖ ≠ p: a a a b c 这时, 也错过匹配成功的机会。如果取k=3, 那么在执行下面的匹配时, 将出现如下的比较序列: t: a a a a b c d e ‖ ‖ ‖ ‖ ‖ p: a a a b c 比较结果得到一个成功的匹配。在这里, 让p［k］与t［i］(
文档评论（0）