第17讲--m序列与BM算法(密码学)教学文稿

BM算法详解BM算法 后缀匹配，是指模式串的⽐较从右到左，模式串的移动也是从左到右的匹配过程，经典的BM算法其实是对后缀蛮⼒匹配算法的改进。

为了实现更快移动模式串，BM算法定义了两个规则，好后缀规则和坏字符规则，如下图可以清晰的看出他们的含义。

利⽤好后缀和坏字符可以⼤⼤加快模式串的移动距离，不是简单的++j，⽽是j+=max (shift(好后缀), shift(坏字符)) 先来看如何根据坏字符来移动模式串，shift(坏字符)分为两种情况：坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下⼀个字符，继续⽐较，如下图：坏字符出现在模式串中，这时可以把模式串第⼀个出现的坏字符和母串的坏字符对齐，当然，这样可能造成模式串倒退移动，如下图： 此处配的图是不准确的，因为显然加粗的那个b并不是”最靠右的”b。

⽽且也与下⾯给出的代码冲突！我看了论⽂，论⽂的意思是最右边的。

当然了，尽管⼀时⼤意图配错了，论述还是没有问题的，我们可以把图改正⼀下，把圈圈中的b改为字母f就好了。

接下来的图就不再更改了，⼤家⼼⾥有数就好。

为了⽤代码来描述上述的两种情况，设计⼀个数组bmBc['k']，表⽰坏字符‘k’在模式串中出现的位置距离模式串末尾的最⼤长度，那么当遇到坏字符的时候，模式串可以移动距离为： shift(坏字符) = bmBc[T[i]]-（m-1-i)。

如下图： 数组bmBc的创建⾮常简单，直接贴出代码如下：1 void preBmBc(char *x, int m, int bmBc[]) {23 int i;45 for (i = 0; i < ASIZE; ++i)67 bmBc[i] = m;89 for (i = 0; i <= m - 1; ++i)1011 bmBc[x[i]] = m - i - 1;1213 } 代码分析：ASIZE是指字符种类个数，为了⽅便起见，就直接把ASCII表中的256个字符全表⽰了，哈哈，这样就不会漏掉哪个字符了。

密码学（Cryptology）课程代码：4241047学分：3学时：48 （其中：课程教学学时：36,实验学时：12）先修课程：高等数学、离散数学、计算机网络适用专业：计算机科学与技术教材：无开课学院：计算机与软件学院一、课程性质与课程目标（一）课程性质密码学是学院开设的一门专业方向选修课程，为学生开展个性化学习提供专业方向，实现个性化分类培养。

本课程主要研究密码学的基础知识、传统密码学技术、常用的加解密算法，是学生了解网络平安过程中一门重要的理论和实验课程。

（二）课程目标课程目标包括知识目标和能力目标，具体如下：课程目标1:能够熟悉密码学中加解密算法的基本原理，熟悉加解密算法的推导，应用加解密算法实现加密系统的设计与实现，培养学生解决具体工程问题的能力。

课程目标2：能够了解密码学与信息平安之间的关系，针对网络环境中信息保护等问题研究和设计可行的加密系统，并对解决方案惊醒分析和论证。

（三）课程目标与专业毕业要求指标点的对应关系本课程支撑专业培养计划中的毕业要求指标点2.1和7.2o毕业要求指标点2.1：应用数学、自然科学和工程科学的基本原理，针对一个系统或者过程进行抽象、分析与识别，并进行问题推理、求解和验证。

毕业要求指标点72 了解信息化与环境保护的关系，能够理解和评价计算机专业工程实践对环境和社会可持续开展的影响。

本课程教学内容包括：密码学的基础知识、传统密码学技术、分组密码、序列密码、哈希函数和消息认证、公钥密码体制、数字签名技术。

附录1:实验考核方式及评分细那么本实验以考查为主，考核的内容包括实验过程的表现（其中包含分析与解决问题的能力）、实验报告的质量等。

分析与解决问题的能力采用提问和现场操作的方式进行。

实验成绩中出勤、预习占10%,实验过程表现占60%、实验报告及思考题占30%。

本课程基本要求是：了解密码学开展过程、基础知识，其与信息平安的关系；了解常用的加解密方法，掌握其含义、数学原理、推导过程并编程实现；针对网络环境中的实际应用，设计并实现加密系统。

《密码学》课程教学大纲Cryprtography课程代码：课程性质：专业方向理论课/必修适用专业：信息安全开课学期：5总学时数：56总学分数：3.5编写年月：2006年6月修订年月：2007年7月执笔：李锋一、课程的性质和目的本课程是信息与计算科学专业信息安全方向的主要专业方向课。

其主要目的研究实现是让学生学习和了解密码学的一些基本概念，理解和掌握一些常用密码算法的加密和解密原理，认证理论的概念以及几种常见数字签名算法和安全性分析。

本课程涉及分组加密、流加密、公钥加密、数字签名、哈希函数、密钥建立与管理、身份识别、认证理论与技术、PKI技术等内容。

要求学生掌握密码学的基本概念、基本原理和基本方法。

在牢固掌握密码学基本理论的基础上，初步具备使用C或C++语言编写基本密码算法（SHA-1、DES、A ES、RC5等）的能力，要求学生通过学习该课程初步掌握密码学的理论和实现技术，使当代大学生适应社会信息化的要求，能利用密码技术服务于社会。

二、课程教学内容及学时分配第1章密码学概论(2学时)要求深刻理解与熟练掌握的重点内容有：1.信息安全的基本概念，2. 密码学的基本概念，3.与密码学有关的难解数学问题。

要求一般理解与掌握的内容有：信息安全的基本内容、密码体制分类、密码学的发展历史。

重点：密码体制的分类。

难点：密码体制的攻击类型理解。

第2章古典密码体制（2学时）本章主要了解1949年之前的古典密码体制，掌握不同类型的加密方式，并了解和认识无条件安全及古典密码的破译。

本章知识点：代换密码（分类和举例）、置换密码（列置换密码、周期置换密码）、古典密码的破译、无条件安全的一次一密体制。

要求学生能够使用C、C++编写Caesar 密码算法，练习最基本或最简单的加密模式。

为进一步加强对加密算法的理解，课堂上演示实现的Caesar密码。

第3章现代分组密码（10学时）要求掌握分组密码概述，主要使用的结构及模式，详细学习DES、IDEA、RC5、AES算法的流程，特别是如何实现这些算法，并了解每个算法的安全性及其效率。

密码学教学大纲一、课程名称密码学（Cryptology）二、课堂授课学时与学分学时：54学分：3三、授课对象信息安全专业3年级本科生四、先修课程高级语言程序设计、信息安全数学基础、计算机原理、通信原理五、教学目的随着计算机和计算机网络在军事、政务、金融、商业等部门的广泛应用，社会对计算机的依赖越来越大，如果计算机系统的安全受到破坏将导致社会的混乱并造成巨大损失。

然而，目前敌对势力的破坏、计算机病毒泛滥、黑客入侵、利用计算机犯罪等危害计算机系统安全的现状是十分严重的。

因此，确保计算机系统的安全已成为世人关注的社会问题并成为计算机科学的热点研究课题。

我国政府十分重视信息安全技术和产业的发展，并把它列入我国优先发展的领域。

密码技术是信息安全的关键技术之一。

密码技术是一门古老的技术，大概自人类社会出现战争便产生了密码。

战争和科学技术的进步推动了密码学的发展。

计算机和计算机网络的广泛应用，电子政务、电子商务的发展给密码学开拓了广泛的应用空间，从而使密码学进入了空前繁荣的阶段。

本课程讲授密码学的基本理论和基本应用技术。

七、主要内容、基本要求、实验内容及学时分配主要内容：1、概论：信息安全的概念。

2、密码学的基本概念：密码学的基本概念，古典密码，古典密码的统计分析。

3、分组密码：数据加密标准（DES），高级数据加密标准（AES），我国商用密码SMS4，分组密码的应用技术。

4、序列密码：序列密码的概念，线性移位寄存器密码，非线性序列密码，有限状态自动机密码，RC4密码。

5、公开密钥密码：公开密钥密码的概念，RSA密码，ELGamal密码，ECC密码。

6、数字签名：数字签名的概念，利用公开密钥密码实现数字签名，美国数字签名标准（DSS）。

7、认证：认证的概念，站点认证，报文认证，身份认证。

8、密钥管理：密钥管理的概念，传统密码的密钥管理，公开密钥密码的密钥管理，公开密钥基础设施（PKI）。

基本要求：本课程主要讲授密码学的基本理论、一些有代表性的密码体制以及密码的应用技术，因此要求学生通过本课程的学习掌握密码学的基本理论和基本应用技术。

合肥工业大学硕士学位论文M序列的构造原理及方法姓名：***申请学位级别：硕士专业：计算数学指导教师：***2003.4.1Ｍ序列的构造原理及方法揍要ｄｅＢｒｕｉｊｎ序列是一类最长的非线性移位寄存嚣廖列，也拣它为Ｍ序列。

它在密码学、电汛学等很多领域中有着广泛的威用，因此，如何有效地生成这类序列是一个很有意义的问题。

本文觚生成橱法、剪接法、并匿法等螽度探讨了Ｍ痔剜的构造藏理与方法。

著利蹋蓑匿滋，在缝轮换移豫寄存嚣斡状态躁中，定义了圈懿“夫妻数”，势裂用·ｒ失妻数”的特性，给出了２元Ｍ序列的一个新的生成算法。

＆算法能生成２”帆”个ｎ级械其中…““’，∞＝ｎ－２１－６－ＭＩ２Ｔｇ（ｎ２１６－腊１１乒２５““”个ｎ级序列，其中≤ｓ≤，，ｓ）兰二型．＝旦Ｉ４关键溺：垒畿掰，、并蕊，、获态窝，、稀获态ＴｈｅＰｒｉｎｃｉｐｌｅｓａｎｄＭｅｔｈｏｄｓｏｆＣｏｎｓｔｒｕｃｔｉｎｇＭＳｅｑｕｅｎｃｅｓＡｂｓｔｒａｃｔｄｅＢｍｉｊｎｓｅｑｕｅｎｃｅｓ，ｉｅ．Ｍｓｅｑｕｅｎｃｅｓ，ａｔｅｔｈｅｌｏｎｇｅｓｔｎｏｎｌｉｎｅａｒｓｈｉｆｔｒｅｇｉｓｔｅｒｓｅｑｕｅｎｃｅｓ．Ｔｈｅｙｃａｎｂｅｕｓｅｄｉｎｍａｎｙｆｉｅｌｄｓｓｕｃｈａｓｃｒｙｐｔｏｇｒａｐｈｙ、ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ．Ｓｏ，ｉｔｉｓｓｕｃｈａｓｉｇｎｉｆｉｃａｔｉｏｎｑｕｅｓｔｉｏｎｔｏｆｉｎｄｈｏｗｔｏｃｏｎｓｔｒｕｃｔｔｈｉｓｓｅｑｕｅｎｃｅｓ．ＴｈｉｓｐａｐｅｒｓｔｕｄｉｅｓｓｏｍｅｐｒｉｎｃｉｐｌｅｓａｎｄｍｅｔｈｏｄｓｏｆｃｏｎｓｔｒｕｃｔｉｎｇＭｓｅｑｕｅｎｃｅｓ，ｂｙｇｅｎｅｒａｔｉｎｇｓｐａｎｎｉｎｇｔｒｅｅｓ，ｏｒｕｓｉｎｇＣＵｔ－ｊｏｉｎｍｅｔｈｏｄ，ｏｒｊｏｉｎｉｎｇｔｈｅｃｙｃｌｅｓｏｆｔｈｅｆａｃｔｏｒｏｆＧ，，Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅｐａｉｒｓｏｆｃｙｃｌｅｓｏｆＧａｒｅｄｅｆｉｎｅｄＢｙｕｓｅｏｆｔｈｅｃｈａｒａｃｔｅｒＰ。

m序列码组-概述说明以及解释1.引言1.1 概述引言部分是一篇文章的开端，旨在介绍读者概述本文内容，引起读者的兴趣。

在本文中，我们将讨论m序列码组的相关内容。

m序列码组是一种特殊的二进制序列，在通信与信息处理领域具有广泛的应用。

通过对m序列码组的研究，我们可以更好地理解其在信号处理、编码与解码、加密等方面的重要作用。

此外，本文还将探讨m序列码组的定义、特点和应用，并展望其未来发展趋势。

总的来说，m序列码组在现代通信领域中扮演着至关重要的角色，因此加深对其理解对于相关领域的研究和应用具有重要意义。

希望通过本文的介绍，读者能够对m序列码组有更深入的认识，并对其在通信与信息处理领域的应用有更清晰的了解。

1.2 文章结构文章结构部分的内容：本文将主要分为三个部分：引言、正文和结论。

1. 引言部分将介绍m序列码组的概述、文章结构和目的，为读者提供一个背景和导向。

2. 正文部分将详细讨论m序列码组的定义和特点，以及其在实际应用中的重要性和作用。

3. 结论部分将总结m序列码组在通信和数据传输领域的重要性，展望其未来发展方向，最后对全文进行一个简要的总结和回顾。

1.3 目的本文的目的是探讨m序列码组在通信和数据存储领域的重要性和应用。

通过对m序列码组的概述、特点和应用进行分析，我们希望能够让读者深入了解这一编码方法的原理和优势，从而为其在实际工程应用中提供参考和指导。

同时，我们也将展望m序列码组未来的发展方向和趋势，为读者提供对m序列码组技术的前瞻性认识。

通过本文的阐述，我们希望能够促进m序列码组技术在通信和数据存储领域的进一步应用和发展，为相关领域的研究和实践工作提供支持和启发。

2.正文2.1 什么是m序列码组m序列码组是一种特殊的二元码组序列，也称为二元伪随机序列。

在数字通信和密码学领域中，m序列码组被广泛应用于信号生成、加密和解密等领域。

m序列码组的生成是通过特定的线性反馈移位寄存器（LFSR）实现的。

m序列由特定的移位寄存器和串行加法器组成，移位寄存器中的多个寄存器会根据特定的反馈规则相互移位并产生序列码组。

《密码学》教学大纲.docx《密码学》教学大纲《Cryptography 》课程编号： 2180081学时： 48学分： 2.5授课学院：软件学院适用专业：软件工程教材（名称、主编或译者、出版社、出版时间）：[1]Wade Trappe, Lawrence C. Washington,Introduction to cryptographywith coding theory, Prentice-Hall (科学出版社影印 ), 2002 。

[2]Alfred J. Menezes, Paul C. van Oorschot ，Scott A. Vanstone, Handbookof applied cryptography, CRC Press, 1997。

主要参考资料：[1]卢开澄，计算机密码学- 计算机网络中的数据保密与安全，清华大学出版社，2003。

[2]Bruce Schneie 著，吴世忠，祝世雄，张文政等译，何德全审校，应用密码学- 协议、算法与 C 源程序，机械工业出版社， 2000。

[3]Steve Burnett, Stephen Pain 著，冯登国，周永彬，张振峰，李德全等译，密码工程实践指南，清华大学出版社， 2001。

[4]Paul Garret 著，吴世忠，宋晓龙，郭涛等译，密码学导引，机械工业出版社，2003。

[5]Wenbo Mao 著, 王继林，伍前红等译，王育民，姜正涛审校，现代密码学理论与实践，电子工业出版社， 2004。

一．课程的性质、目的及任务密码学是软件工程专业拓宽、提高性的专业选修课。

大量的信息以数据形式存放在计算机系统中并通过公共信道传输。

保护信息的安全已不仅仅是军事和政府部门感兴趣的问题，各企事业单位也愈感迫切。

密码技术是信息安全中的关键技术，它的有效使用可以极大地提高网络的安全性。

课程的目的在于为已经或即将完成计算机学位基础课程并计划从事信息安全工程实践或理论研究的学生提供基础指导。

m 序列及相关理论分析摘要：本文阐述了常用伪随机序列m 序列的产生方法，对其自相关性和互相关性等主要性质进行简要分析。

关键字：m 序列；伪随机序列；相关性；m code sequence and relevant theory analysesAbstict : This paper expounds the generation method of commonly used pseudo-random sequence: m sequence and carries the brief analys on auto correlation mutual correlation.Keywords :m sequence; pseudo-random sequence; correlation1 引言在通信系统中，随机噪声会使数字信号出现误码和使模拟信号产生失真和，而且随机噪声也是限制信道容量的一个重要因素。

因此人们经常希望消除或减少通信系统中的随机噪声。

另一方面，在实际需要时人们产生随机噪声并利用随机噪声。

例如，在实验室中可能要故意加入一定的随机噪声对通信设备或系统的各个性能指标进行测试。

又如通过利用掺入随机噪声来提高通信的可靠性。

为了满足上述实际应用要求，则需要产生满足对应要求的随机噪声信号。

实际中，难以重复产生和处理随机噪声是利用随机噪声的最大困难。

2 m 序列的产生m 序列又称伪随机序列、伪噪声码(PN)或伪随机码。

其中：确定序列是可以预先确定并且可以重复实现的序列；随机序列是既不能预先确定又不能重复实现的序列；伪随机序列是不能预先确定但可以重复产生的序列。

m 序列（全称：最长线性反馈移位寄存器序列）是最为常用的一种伪随机序列。

m 序列是由带线性反馈的移位寄存器产生的序列，并且具有最长的周期。

由n 级串接的移位寄存器和对应级别的反馈逻辑电路可组成动态移位寄存器，如果反馈逻辑线路只用线性模2和构成，那么就称此寄存器为线性反馈移位寄存器；但是反馈逻辑线路中出现如“与”、“或”等运算，那么称此寄存器为非线性反馈移位寄存器。

密码学简明教程课程设计课程概述本课程是一门密码学简明教程，旨在为计算机科学专业的学生提供基础的密码学知识和技能。

本课程包含密码学的基本概念、对称加密算法、非对称加密算法、哈希函数、数字签名和身份验证等方面的内容。

学生可以理解并应用这些知识来保障信息的安全性，从而在实际应用中提高信息系统及网络的安全保障。

本课程分为为三个大模块和十个小章节，学生需要通过本课程的学习，掌握密码学的基本概念，了解加密算法、哈希函数、数字签名及身份验证的原理，并能够应用其中的知识解决实际中的问题。

课程大纲第一模块：基础概念第一章：密码学基础概念本章主要介绍密码学的基本概念和密码学的起源。

学习者将了解一些基本的密码学定义和术语，包括明文，密文，密钥，消息鉴别码以及密钥空间等内容。

第二章：密码学分类本章主要介绍密码学的分类以及密码学的发展历程。

学习者将了解对称密钥加密和非对称密钥加密的概念，并了解它们的优缺点以及应用场景。

第二模块：加密算法第三章：对称密钥算法本章主要介绍对称密钥算法的原理以及如何使用它们进行加密和解密。

涵盖了几个流行的加密算法，包括DES，AES等。

第四章：非对称密钥算法本章主要介绍非对称密钥算法的原理以及如何使用公钥和私钥进行加密和解密。

学习者将了解RSA算法、ElGamal算法、椭圆曲线密码等算法。

第三模块：密码学应用第五章：哈希函数本章主要介绍哈希函数的原理以及如何使用它们进行消息摘要和数字指纹。

学习者可以了解Hash算法（如MD5，SHA-1等）的原理，摘要算法，以及攻击技术和防御技巧。

第六章：数字签名和验证本章主要介绍数字签名和验证的原理以及如何实现。

学习者将理解数字签名的原理和数字证书的结构，学习基于RSA算法的数字签名，如MD5、SHA-1等。

第七章：身份验证本章主要介绍身份验证的基本原理和现代实现技术。

学习者将了解各种身份验证协议以及它们的安全属性、优点和缺点。

学习者也将了解单因素身份验证和多因素身份验证技术的特点和应用场景。

信息安全序列密码课程设计一、课程目标知识目标：1. 理解序列密码的基本概念、原理及其在信息安全中的应用。

2. 掌握序列密码的加密与解密方法，包括线性反馈移位寄存器（LFSR）和非线性反馈移位寄存器（NLFSR）。

3. 了解序列密码的安全性分析及其相关攻击手段。

技能目标：1. 能够运用所学知识设计和实现简单的序列密码算法。

2. 能够分析并评价给定序列密码算法的安全性。

3. 培养学生的逻辑思维能力和问题解决能力，使其在复杂问题中运用所学知识进行创新设计。

情感态度价值观目标：1. 培养学生对信息安全领域的兴趣，激发他们主动探索和学习的热情。

2. 增强学生的信息安全意识，使其认识到密码学在保护信息安全中的重要作用。

3. 培养学生的团队合作精神和批判性思维，提高他们在实际应用中分析问题、解决问题的能力。

课程性质分析：本课程为高中信息技术课程，旨在让学生了解和掌握信息安全基础知识，特别是序列密码的相关内容。

课程注重理论与实践相结合，强调学生的实际操作和动手能力。

学生特点分析：高中学生已具备一定的信息技术基础，对信息安全领域充满好奇心，具有较强的学习能力和探究精神。

在此基础上，本课程旨在提高学生的理论水平和实践能力。

教学要求：1. 结合课本内容，深入浅出地讲解序列密码相关知识。

2. 设计丰富的教学活动，引导学生主动参与，提高他们的实践操作能力。

3. 注重培养学生的逻辑思维和问题解决能力，将所学知识应用于实际情境。

4. 定期进行课程评估，确保学生达到预期学习成果。

二、教学内容1. 序列密码基本概念：介绍序列密码的定义、分类及其在信息安全中的应用场景。

- 教材章节：第二章第一节- 内容：线性反馈移位寄存器（LFSR）、非线性反馈移位寄存器（NLFSR）2. 序列密码算法原理：讲解序列密码的加密与解密原理，以典型算法为例进行分析。

- 教材章节：第二章第二节- 内容：序列密码加密流程、解密流程、典型算法（如 Vernam 密码）3. 序列密码安全性分析：探讨序列密码的安全性，介绍相关攻击手段及防范策略。

m序列初始值
摘要：
一、引言
二、m 序列的定义与性质
三、m 序列的初始值
四、m 序列在通信和密码学中的应用
五、结论
正文：
m 序列是伪随机数序列中的一种，具有很好的伪随机性和长周期性，被广泛应用于通信和密码学等领域。

在研究m 序列的性质和应用时，首先需要了解m 序列的初始值。

m 序列的定义如下：
X(n+1) = (m - X(n)) mod m
其中，m 为序列的长度，X(n) 为序列的第n 项。

m 序列具有以下性质：
1.周期性：m 序列的最小正周期为m。

2.非线性：m 序列的生成公式具有非线性特性。

3.平稳性：当m 足够大时，m 序列的分布趋于平稳。

4.相关性：m 序列的前后两项之间具有较强的相关性。

m 序列的初始值是指在序列生成之初，各项的取值。

对于m 序列，我们可以通过初始值来描述其状态。

在实际应用中，通常需要根据实际需求来选择
合适的初始值。

m 序列在通信和密码学中有广泛的应用，如：
1.通信领域：m 序列可以用于数字调制、信号解调、信道均衡等。

2.密码学领域：m 序列可以用于流密码的设计、伪随机数生成器等。

综上所述，m 序列是一种具有良好伪随机性和长周期性的数列，其初始值的选择对序列的性能具有重要影响。

BM算法是一种精确字符串匹配算法（区别于模糊匹配）。

BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。

BM算法的基本流程: 设文本串T，模式串为P。

首先将T与P进行左对齐，然后进行从右向左比较，如下图所示:若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。

下面，来详细介绍一下坏字符规则和好后缀规则。

首先，诠释一下坏字符和好后缀的概念。

请看下图：图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。

1）坏字符规则（Bad Character）：在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论：i. 如果字符x在模式P中没有出现，那么从字符x开始的m 个文本显然不可能与P匹配成功，直接全部跳过该区域即可。

ii. 如果x在模式P中出现，则以该字符进行对齐。

用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。

例1：下图红色部分，发生了一次不匹配。

计算移动距离Skip(c) = 5 - 3 = 2，则P向右移动2位。

移动后如下图：2）好后缀规则（Good Suffix）：若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论：i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现，且位置t'的前一个字符与位置t的前一个字符不相同，则将P右移使t'对应t方才的所在的位置。

ii. 如果在P中任何位置已匹配部分P'都没有再出现，则找到与P'的后缀P''相同的P的最长前缀x，向右移动P，使x对应方才P''后缀所在的位置。

用数学公式表示，设Shift(j)为P右移的距离，m为模式串P的长度，j 为当前所匹配的字符位置，s为t'与t的距离（以上情况i）或者x与P''的距离（以上情况ii）。