摘要：首先在 system.reg 里手动添加
[Software\\Microsoft\\Windows NT\\CurrentVersion\\FontLink\\SystemLink] 1150441842
"Tahoma"=str(7):"simsun.ttf,\x5b8b\x4f53\0msgothic.ttc,MS UI Gothic\0mingliu.ttc,PMingLiU\0"
其中simsun.ttf 换成你喜欢的字体, \x5b8b\x4f53 换成这个字体中文名字的 UNICODE 编码(老版本 WINE 用英文, 比如 SimSun)
然后运行 regedit, 在 HKEY_LOCAL_MACHINE\software\microsfot\windows nt\currentversion\fontsubstitutes 里加上
MS Shell Dlg(类型是 REG_SZ, 值是SimSun) （全文共662字）——点击
此处阅读全文
设计模式重读:
什么是设计模式:
解决某个问题的方案
每个模式有四个特征:
模式名
问题
解决方案
效果
MVC的设计模式:
界面设计中经常会使用类的模型/视图/控制器 (Model/View/Controller) 这三个东西.
Model可以看成是一个对象, View是它的显示, Controller是它的输入的响应
设计的原则:
把易变的部分与不变的部分分开, 使程序易于扩展
让对象间的耦合度降低，使一个对象的修改不会影响另外一个对象
复用的要点:
1 对接口而不是对实现编程
优点是:
客户不须知道他们使用的对象的特定类型，只知道对象有期望的接口
客户不须知道他们使用的对象是用什么类来实现的, 只知道定义接口的抽象类
结果可以避免各系统的依赖关系
2 优先使用对象组合成不是类继承
继承是通过对父类进行具体化来实现功能,继承在编译时确定，并且继承知道父类的实现,使子类与父类的依赖关系很紧密, 所以后面如果想维护时不好修改
组合是组装或是组合对象来实现更复杂的功能, 组合时只需要知道对象的接口实现的功能，而不需要知道对象的具体实现,所以依赖更少
委托是有两个对象参与处理一个请求,接收请求的对象把操作委托给它的代理者. 它是组合的一种对例
3 参数化类型
参数化类型是定义一个类型时不指定该类型所使用到的其它所有类型，未指定的类型在使用时以参数提供，这就是c++中的模板
这个一般用于解决操作时步骤基本相同,只是类型不同的场合,想更多的理解可以看STL库
4 聚合与相识
聚合表示一个对象拥有另一个对象或是对另一个对象负责
相识则是一个对象仅知道另一个对象, 有时也叫"关联" 或 "引用"
相识比聚合的耦合性要弱
模式的分类;
可以分成三类:
创建型模式: 用于对象过程的模式
结构型模式: 用于把不同的类或对象组合起来实现更复杂的功能
行为型模式: 用于规定不同类或对象间的交互方法或是职责，与结构型模式不同的是行为型模式中的对象是平行的,它们是交互的关系，而在结构型中它们是组合的关系，并且可能是包含的关系
/*-----------------------------------------------------------------------------
*
* 创建型模式 (用户类或对象的创建过程的模式)
*
*-----------------------------------------------------------------------------*/
对象创建型模式: 这个模式用于创建新的对象
特点:
隐藏具体实现: 把具体类的信息封装起来
隐藏创建过程: 隐藏了这些类的实例是如何被创建与放在一起的, 系统只知道这些对象中由抽象类所定义的接口
1 抽象工厂(Abstract Factory) - 对象创建型模式
抽象工厂:
创建一批抽象类的对象的工厂
目的:
提供一个创建一系列相关或相互依赖对象的接口，
而无需指定它们具体的类
实现:
参与者: 工厂Factory, 产品Product
Product是一批抽象类, 定义了产品的接口
Factory提供产生Product的方法
具体的Factory提供产生实例化的Product的方法
例子:
如gvim在Windows或是Linux上，窗口外观不一样,
但是窗口的组成部分基本一样(如都有标题栏,菜单,编辑区等),
相同控件的功能基本一样(如菜单的功能), 并且控件间可能有关联
这可以定义标题栏，菜单, 编辑区的抽象类定义它们的功能, 然后定义一套接口产生这些抽象类
2 生成器(Builder) - 对象创建型模式
生成器:
使用导向器引导类的创建过程,为相同的类创建不同对象的方法
目的:
将一个复杂对象的构建与它的表示分离,
使得同样的构建过程可以创建不同的表示
实现:
参与者:导向者director与生成器builder.
builder在构造函数中只进行基本的功能,
同时提供了其它接口进行对象的初始化,
director引导builder的构造过程,
调用builder的构造函数与其它初始化函数来创建builder,
并返回builder对象
class Builder{
public:
Builder(); // 构造函数
void BuildPartA(); // 初始化函数,初始化到状态A
void BuildPartB(); // 初始化函数,初始化到状态B
...
};
class Director{
public:
...
Builder* CreateBuilder1(){ // 引导生成的对像的构建过程
Builder* p = new Builder;
p->BuildPartA();
return p;
}
Builder* CreateBuilder2(){ // 引导生成的对像的构建过程
Builder* p = new Builder;
p->BuildPartB();
return p;
}
Builder* CreateBuilder3();
};
从上面的例子可以看出, builder只是提供基本的构造函数. 而具体生成怎样的builder由director决定. director封装了builder构造过程
builder模式把构造代码与表示代码分开, 因为builder的构造函数中并没有进行完整的构造, builder的构造是在director的CreateBuilderX中进行的. 你可以对它进行更多的订制.
我想这个应该适合一个对象可以有多个状态表示的时候. 如房间类, 假设内部的物品是一样的, 但不同的摆设会形成不同的房间. 而builder模式中使用director就可以为房间类导向而为每个房间生成不同的对象.
3 工厂方法(Factory Method) - 对象创建型模式
工厂方法:
creator的子类提供方法生产product对象
目的:
定义一个用于创建对象的接口，让子类决定实例化哪个类.Factory method使一个类的实例化延迟到子类
实现:
需要两个参与者:创建者creator与产品product,
1 product 对象定义基本的接口,
2 creator 定义创建 product 的接口.
3 creator 的子类实例化创建 product 的接口.
应用:
一般,如果creator与product有联系的话, 会使用这种方法.如在界面开发中的程序文档关系(Application,document,这个在Windos开发中经常会看到).
4 原型(ProtoType) - 对象创建型模式
原型:
通过调用原型的Clone方法创建新的对象,
新的对象不需要再进行其它特别的初始化(就达到与原型相同的状态)
目的:
用原型实例指定创建对象的种类, 并且通过拷贝这些原型创建新的对象
实现:
原型类提供一个Clone操作可以用来Clone自身状态
原型对象可能经过特别的初始化后才达到当前状态, 但下一个对象直接调用原型对象的Clone就可以直接达到这个状态而不需要再进行特别的初始化
应用:
这个方法一般用在系统中有几类不同的对象组成,这些对象区别的只是它们的状态, 如音符
5 单件(Singleton) - 对象创建型模式
单件:
类的实例只有并且只会有一个
目的:
保证类只有一个实例, 并提供一个访问它的全局访问点
实现:
c++中声明类的构造函数为非public的, 并且提供一个friend方式或是类的static方法来创建实例.
应用:
如果系统中一个类有多个实例会有问题, 就使用这个方法吧, 这样可以避免后面维护的人产生错误
/*-----------------------------------------------------------------------------
*
* 结构型模式
*
*-----------------------------------------------------------------------------*/
结构型模式: 通过组合类或对象来获得更大的结构并且得到新的功能
结合类的叫类对象结构型模式
结合对象的叫对象结构型模式
1 适配器(Adapter) - 类对象结构型模式
适配器:
用一个包装器Wrapper封装另外一个类并提供用户所希望的接口
目的:
将一个类的接口转换成客户希望的另外一个接口. Adapter模式使得原来由于接口不兼容而不能一起工作的那些类可以工作
实现:
定义一个新类Wrapper封装旧类，
新类通过调用旧类接口来提供用户希望的接口
2 桥接(Bridge) - 对象结构型模式
桥接:
类的抽象部分与实现部分都可以独立的变化
目的:
将抽象部分与它的实现部分分离, 使它们都可以独立的变化
原因;
当一个抽象可能会继承，
并且它的实现也有多种方式时，
它的抽象与实现都需要独立变化,
这时为了简化继承(而不是每个实现都有一个继承)，
可以使用桥接的技术让实现也抽象化可以独立的变化,
而抽象部分也可以独立的变化
实现:
参与者:抽象Abstraction与实现Implementor
Abstraction定义抽象类的接口，并且维护一个指南Implementro类型对象的指针
Implementor定义实现类的接口, 该接口不一定要写Abstraction的接口一致. 一般来讲, Implementor接口仅提供基本操作，而Abstraction则定义了基于这些基本操作的较高层次的操作
作用: 如果你希望两个部分都可以独立变化的话, 那就用Bridge吧(一般是抽象有继承的条件下, 并且抽象的实现也需要变化的时候)
如果实现是固定的, 那直接使用继承就可以了不用Bridge
3 组合(Composite) - 对象结构型模式
组合:
操作时不管是对象还是对象的组合都一致同仁，如果是对象的组合的话对象的组合会把操作传到每个对象并返回一个最后的结果的
目的:
把对象组合成树形结构以表示"部分-整体" 的层次结构, 使用户对单个对象和组合对象的使用具有一致性
实现:
定义一个Component抽象类，为组合中的对象声明接口,声明一个接口用于访问和管理Component的子组件
Leaf表示叶节点对象,在组合中定义对象的行为
Composite定义有子部件的那些部件的行为,
并且存储子部件,同时实现与子部件相关的操作
Client通过Component接口操纵组合部件的对象
一个组件可以添加到另外一个组件中从而组成一棵树, 接收到请求时会把请求一层一层往下传直到叶子
解决的问题:
表示部分-整体观点,简化其它部分的操作代码
适用性;
想表示对象的部分-整体层次结构
想用户忽略组合对象与单个对象的不同,用户将统一的使用组合结构中的所有对象
应用;
作者的例子是计算机报价单, 确实使用报价单的话最后对一个组合求价格更方便一些
装饰(Decorator) - 对象结构型模式
装饰:
对象A给对象B添加功能，并且对象A提供的接口与对象B一样
目的:
动态的给一个对象添加一些额外的职责,就增加功能来说，装饰比生成子类更灵活
实现: 参与者:组件Component与装饰者Decorator
Decorator维持一个指向Component对象的指针, 并定义一个与Component接口一致的接口(一般继承相同的抽象类),它将给Component动态的添加职责
应用:
想给一个类扩展一些功能，但是又不想产生子类的时候
在不影响其它对象的情况下以动态透明的方式给单个对象添加职责
处理那些可以撤消的职责
4 外观(Facade) - 对象结构型模式
外观:
为一组接口提供一个一致的界面
目的:
为子系统中一组接口提供一个一致的界面.
Facade定义了一个高层接口, 这个接口使得这一子系统更加容易使用
原因:
把一个系统分成若干个子系统有利于降低系统的复杂性，
为了让子系统间的通信与相互依赖关系达到最小，
使用外观的方法可以为子系统提供一个单一而简单的界面
结果:
让这个子系统与外界的耦合性最小, 并且这组子系统更容易使用
其实就像是库的接口那样,它们提供了一个简单的功能给外面
5 享元(Flyweight) - 对象结构型模式
享元:
不同场景中出现同一个对象,那可以把它们只看成一个对象的共享,场景中只存储它们的外部状态与对这个对象的引用
目的:
运用共享技术有效的支持大量细粒度的对象
实现:
实现一般包括flyweight与flyweightfactory,client三个部分
flyweight是一个共享对象, 它会同时出现在多个场景(context), 并且每个场景中都可以做为一个独立的对象. 但是, 它不能对它所运行的场景做出任何假设。
为了实现flyweight对象, 可以把flyweight的状态分成内部状态与外部状态, 独立于场景的就叫内部状态，flyweight只保存内部状态. 与场景相关的就叫外部状态, 用户在调用时把外部状态传给Flyweight
flyweightfactory创建并管理flyweight对象
client维持对flyweight的引用，并且存储一个或多个flyweight的外部状态
例子:
如一个字处理器,它的享元是每个字符, 内部状态是字符值，外部状态是这个字的位置，大小等
作用: 理论就是如果一个对象需要在多个地方出现，并且只有状态不同时，可以使用享元的办法把内部状态保存在享元中，外部状态在调用这个对象时传入
可以减少系统中对象的数目
6 代理(Proxy) - 对象结构型模式
代理: 控制对另外一个对象的访问
目的; 为其它对象提供一个代理以控制对这个对象的访问
实现: 跟经济人的意思差不多, 也就是因为某种原因而不想让其它人直接访问主角而采取的一种措施
/*-----------------------------------------------------------------------------
*
* 行为模式
*
*-----------------------------------------------------------------------------*/
行为模式: 描述对象或类间行为的模式
行为类模式: 使用继承机制在类间分派行为
行为对象模式: 使用对象复合而不是继承来实现:
1 一组对等的对象怎样想到协作以完成其中任一个对象都无法完成的任务
2 把行为封状在一个对象中并将请求指派给它
1 职责链(Chain of responsibility) - 对象行为型模式
职责链:
多个对象连成一条链, 每个请求都在这条链中从头到尾传送直到有对象处理它为止
目的:
把发送者与接收者的耦合去掉
使多个对象都有机会处理请求。装这些对象连成一条链，并沿着这条链发送请求，直到有一个对象处理它为止。
应用:
多个对象可以处理一个请求，哪个对象处理该请求运行时自动确定
想在不明确指定接收者的情况下，向多个对象中的一个提交请求
可处理一个请求的对象集合应该被动态指定
2 命令(Command) - 对象行为型模式
命令: 每个请求都是一个对象,对于过程语言则是每个请求都有一个回调关联
目的: 将一个请求封装成一个对象，从而使你可用不同的请求对客户进行参数化，对请求排队或记录请求日志，及支持可撤消的操作
功能: 你可以进行命令排队, 你可以添加取消命令的功能,同时可以快速的增加新命令
3 解释器(Interpreter) - 类行为型模式
解释器: 在程序中通过解释另外一种语言来提供对复杂事务的处理
目的: 给定一个语言,定义它的文法的一种表示,并定义一个解释器，这个解释器使用该表示来解释语言中的句子
应用:
在模式匹配中会用到,你可以在网上找到模式匹配实现的鼻祖 - Henry Spencer的代码了解.
同时在一些游戏或程序中也支持脚本, 如魔兽世界支持lua脚本
复杂的文法一般比较难维护，这时一般可以使用lex&yacc来实现(牺牲性能来实现功能)
4 迭代器(Iterator) - 对象行为型模式
迭代器: 不暴露对象的内部表示，而是提供另外方法访问聚合对象内各元素
目的: 提到一个方法顺序访问一个聚合对象中各个元素，而又不城暴露该对象的内部表示
应用: STL中各容器的迭代器
如果你想让用户访问对象内的数据，但是又不想让他们知道这些数据的存放方式的话，可以使用迭代器
5 中介者(Mediator) - 对象行为型模式
中介者：一系列的对象交互通过中介来通信而不是对象间直接通信
目的: 用一个中介对象来封装一系列的对象交互，中介者使各对象不需要显式的相互引用，从而使其耦合松散，而且可以独立的改变它们间的交互
应用: 一个系统中有多个对象它们相互关联，想降低耦合性
6 备忘录(Memento) - 对象行为型模式
备忘录: 用一个对象在不知道另外一个对象内部的情况下保存它的状态
目的: 在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象外保存这个状态，后面可以把这个对象恢复到原先保存的状态
应用; 如果你想恢复一个对象的状态到之前某个状态, 那使用备忘录可能会好点
7 观察者(Observer) - 对象行为型模式
观察者: 多个对象可以订阅当前对象的更新事件通知
目的: 定义对象间一种一对多的依赖关系，当一个对象的状态发行改变时，所有依赖于它的对象都得到通知并被自动更新
实现: 参与者: 目标与观察者
目标提供注册与删除观察者的接口
观察者为需要关注的事件提供更新的接口
应用: 在Symbian中基本上每个事件都可以增加观察者,这样当事件发生时所有观察者都得到通知从而增加开发的灵活性
8 状态(State) - 对象行为型模式
状态: 对象在内部状态改变时改变它的行为
目的: 充许一个对象在其内部状态改变时改变它的行为，对象看起来似乎修改了它的类
应用; 不同状态下, 相同接口的行为不一样时可以用，可以减少子类数目
9 策略(Policy)
策略: 不同的策略有相同的接口从而使它们可以互换
目的: 定义一系列的算法,使它们一个个封装起来，并且它们可以相互替换，本模式使得算法可独立于使用它的客户而变化
10 模板方法(Template method) - 类行为模式
模板方法:把一个操作中不变的部分做为模板，可变的部分由子类完成
目的: 定义一个操作中算法的骨架, 而将一些步骤延迟到其子类中，模板方法使得子类可以不改变一个算法的结构
11 访问者(Visitor) - 对象行为模式
访问者: 通过接受访问者来扩展自己的接口
目的; 表示一个作用于某对象结构中的各元素的操作。它使你在不改变各元素的类的前提下作用于这些元素的新操作。
实现; 有两个对象:visitor与node
visitor提供visit接口,visit接口的参数可以是一个node或是这个node里面的一个对象.
node提供一个accept接口，它将接受一个访问者,并在这个接口里面调用这个访问者的visit函数
这样可以通过添加一个visitor接口来针对node里面的数据进行不同的操作,相当于添加了了node的接口
应用:
一个对象结构包含很多类对象，它们有不同的接口，而你想对这些对象实施一些依赖于其具体类的操作
需要对一个对象结构中的对象进行很多不同的并且不相关的操作，而你想避免让这些操作污染这些对象的类. Visitor使得你可以将相关的操作集中起来定义在一个类中。
使用ollydbg来调试release版本的程序
程序在用release跑时有时会出各种各样的问题, 如果使用debuglog来跟的话, 有时debuglog很多不知道是哪个才是真正出问题的地方, 对于这种情况，推荐一下ollydbg
ollydbg是一个二进制的调试工具, 一般用来反汇编代码及动态跟踪程序.相同的工具还有:
softice(dos窗口,完全手动的调试方法)
w32asm(静态分析代码的好工具, 不过动态跟踪能力不行)
IDA(强大的反汇编工具，但是用起来太复杂了)
windbg(强大的调试工具, 不过个人感觉不够直观)
相对来说ollydbg是里面比较好用的工具,特点如下:
GUI界面,所有的功能都可以通过菜单及右键菜单查找到(比softice要方便)
代码分析, 可以显示寄存器,循环,api调用,表，常量和字符串等(而不只是汇编代码)
可以从map或是lib中加载符号表(没有符号表,那程序中使用到的函数一般是像libc.1234,有了符号表就可以变成libc.printf这样子)
直接加载动态库(IDA需要运行程序时才会把这个程序需要的所有库都加载,ollydbg是打开这个exe就会载入所有使用的动态库)
加大的插件功能
可以自己订制标签，注释和函数描述
可以保存不同会话的补丁(不做cracker,所以这个基本上用不到)
绿色不需要安装
强大的断点功能,除了普通的代码断点外还有内存断点和硬件断点.内存断点可以设置成访问这块内存或是写入这块内存时中断,不过内存断点有时会无效，硬件断点则是再试调试时断点依然存在,
更多的特点可以在它的网站上看到
使用ollydbg来帮助定位错误的步骤:
1 下载与安装
2 把要调试的程序加载到内存(可以使用open或是attach方式)
3 在ollydbg中加载程序的符号表(map文件)和动态库的符号表(lib文件)
4 运行直到出错
5 使用ollydbg查看调用堆栈("查看"->"调用堆栈")定位出错的函数
6 在ollydbg的CPU窗口中定位出错的代码行()
7 查看出错原因, 如调用函数的参数等, 还可以提到windows的getlasterror的值, 帮助定位
8 如果在上一步发现问题所在那是最好, 如果没有发现,可以在附近添加debug log,来帮助定位出错原因
使用:
下载:
在google上查找 "ollydbg 下载", 推荐使用中文版本的, 因为中文版带有很多常用插件并且解决了汉字的问题
安装:
直接解压到某个目录下,然后运行
选择菜单 "选项"->"界面选项",在 "目录" 中设置udd与plugin的绝对路径
界面介绍:
状态栏上有一个命令行窗口,可以直接在这里输入一些命令来简化操作, 当然这些命令实现的功能也可以通过右键菜单来实现
调试前准备:
为了方便的看exe程序的符号, 你需要这个exe的map.
MAP 文件是程序的全局符号、源文件和代码行号信息的唯一的文本表示方法，是整个程序工程信息的静态文本。它可以在任何地方、任何时候使用，不需要有额外的程序进行支持，仅仅通过一个文本阅读工具如Ultra Edit就可以打开了。而且，这是唯一能找出程序崩溃代码行的救星。
那么我们应该如何生成 MAP文件呢？在 VC 中，我们可以按下 Alt+F7，打开“Project Settings”选项页，选择 C/C++ 选项卡，并在最下面的 Project Options 里面输入：/Zd ，然后要选择 Link 选项卡，选中“Generate mapfile”复选框，并在最下面的 Project Options 里面输入：/mapinfo:lines，表示生成 MAP 文件时，加入行信息。最后按下 F7 来编译生成 EXE 可执行文件和 MAP 文件，此时可以在工程的Debug目录下找到刚刚生成的MAP文件，文件名为“工程名.map”。
调试的方法:
ollydbg提供三种调试方法,
1 直接在File->Open菜单里面载入一个程序，然后加好断点后点 Run开始调试
2 在 File->Attach菜单中附加到一个进程，然后开始调试. 注意如果ollydbg退出时这个进程也会被停掉
3 在 选项->实时调试设置里面设置 ollydbg为系统默认的调试器, 然后当程序异常时系统会自动调出ollydbg进行调试.
一般我觉得第三种不一定能保存出错前的堆栈信息.所以最好还是使用第一第二比较保险, 但也有时候堆栈被破坏的
调试步骤:
1 使用ollydbg加载需要调试的程序，可以是open方式打开也可以是attach方式打开
2 使用"插件"->"load map"菜单导入这个exe的map文件,如果这个exe使用了其它动态库，并且有这些动态库的lib文件,在 "调试"->"选择导入库" 里面增加静态库
3 按ctrl+A进行代码分析
4 如果想看程序中的所有函数名等,那可以:
a.在CPU窗口点右键,选择 "查找"-> "当前模块中的名称"或"所有模块中的名称"
b.在命令行中输入sn
5 如果需要加普通断点,有几个方法:
a.直接在cpu窗口中对应的代码那里按F2,或是点右键出来选择"切换断点"
b.如果是想在某个函数的入口添加断点, 那可以在上面弹出的符号窗口中对应的函数点右键, 然后选择"切换断点", 命令行是 "bp 符号名"
c. 如果是想所有调用这个函数的地方加断点, 那在符号窗口中对应的函数点右建, 选择"查找参考", 然后在弹出窗口点右键，选择 "每个参考上设置断点". 命令行是 "bpx 符号名"
6 运行, 等待出错，出错了就查看调用堆栈，看是哪个函数中出错的
7 看当前代码周围有没有什么特殊的东西，如字符串，或是系统api名字等, 这样可以帮助你定位出错的代码行
KMP算法的改进。
KMP算法对朴素算法的改进，在于利用每次已得到的部分匹配:s[k+1..i]=t[1..j],但s[i+1]≠t[j+1]，j<m。它隐含着主串s中从l+1开始的子串不可能与t[1..m]匹配完全，其中l=k,k+1,…，k+j-π[j]-1（即i-π[j]-1）。因而完全匹配的测试可大步地往前推进到s中从i+1-π[j]开始的子串，而且对于它，我们已有部分匹配s[i+1-π[j]..i]= t[1..π[j]]。如果π[j]>0，为扩展这部分匹配，接着需要测试的是s[i+1]=t[π[j]+1]？但已知s[i+1]≠t[j+1]，所以，如果有t[π[j]+1] =t[j+1],那么可以肯定s中i+1-π[j]开始的子串，不可能与t[1..m]完全匹配。因而完全匹配的测试可再次推进到s中从i+1-π[π[j]]开始的子串，且我们再次有与t[1..m]的部分匹配s[i+1-π[π[j]]..i]
=t[1..π[π[j]]]，如果π[π[j]]>0。接着为扩大该部分匹配，需要测试的是s[i+1]= t[π[π[j]]+1]，如果又有t[π[π[j]]+1]=t[j+1]，则完全匹配的测试还可以继续往前推进，直到t[π[π[…[π[j]]…]]+1]≠t[j+1]。
这表明对于已得到的部分匹配：
s[k+1..i]=t[1..j]，s[i+1]≠t[j+1]，j<m …………………………………（3.3.1）
如果 t[j+1]= t [π[j]+1]=…=t[π[π[…[π[j]]…]]+1]……………………（3.3.2）
e
且 π[π[…[π[j]]…]]=0
或 π[π[…[π[j]]…]]≠0但t[j+1]≠t[π[π[π[…[π[j]]…]]]+1]…(3.3.3）
e+1
那么，相应的完全匹配的测试可以直接推进到s中从i+2或i+1-π[π[π[…[π[j]]…]]]
e+1
开始的子串，且对后一种情况，该子串与t[1..m]已有部分匹配:
s[i+1-π[π[π[…[π[j]]…]]]..i] =t[1..π[π[π[…[π[j]]…]]]]
e+1
e+1
，而接着为扩大部分匹配需要做的测试是比较
s[i+1]与t[1]或s[i+1]与t[π[π[π[…[π[j]]…]]]+1]。
e+1
换句话说，在满足（3.3.1）、（3.3.2）、（3.3.3）且e≥1的情况下，完全匹配的测试允许比KMP算法有更大步的推进，即KMP算法可以作进一步的改进。
从上面的分析，我们不仅看到KMP算法可以进一步改进，而且可看出相应的改进措施：在原前缀函数π[q]的基础上，引入修改的前缀函数π’[q],q=1,2,3,…,m.
π’[π[q]] 当π[q]≠0且t[q+1]=t[π[q]+1]
π’[q]=
π[q]
当π[q]=0或t[q+1]≠t[π[q]+1]
修改后的前缀函数（Modified_Prefix_function）可实现如下：
Proc.
Modified_Prefix_function（var t:string； var ppi: array[1..t.length] of integer）；
var m,q,k:integer；
pi:
array[1..t.length] of integer；
begin
compute-Prefix-function(t,pi)；
m:=t.length；
for q:=1
to m do
begin
k:=pi[q]；
while
k>0 and t.chs [q+1]=t.chs[k+1]
do k:=pi[k]；
ppi[q]:=k
end
end；
KMP算法相应的改进只要将调用函数compute_Prefix_function改为调用函数Modified
_Prefix_function，其他地方不作任何修改。
经过修改后的KMP算法，在最坏情况下的时间复杂性虽然没有明显改进，但对于那些使π’[q]<π[q]的t[1‥m]将有明显改进，而且π[q]-π’[q]越大改进越明显。例如s=’aaaabaaaaab’,t=’aaaaab’
|
|
1
|
2
|
3
|
4
|
5
|
6
|
|
|
|
π
|
0
|
1
|
2
|
3
|
4
|
0
|
|
|
|
π’
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
完全匹配从对s的子串s[1..6]进行测试开始，在得到部分匹配s[1..4]=t[1..4],s[5]≠t[5]，排除s[1..6]与t[1..6]完全匹配的可能之后，若按原KMP算法，要依次分别比较s[5]与t[4]，s[5]与t[3]，s[5]与t[2]，和s[5]与t[1]，依次排除s[2..7]，s[3..8]，s[4..9]和s[5..10]与t[1..6]完全匹配的可能，才能推进到测试s[6..11]与 t[1..6]的完全匹配而得到需要的结果。若按修改的KMP算法，由于4+1-π’[4]=5，马上可排除s[2..7]，…，s[4..9]与t[1..6]完全匹配的可能，将完全匹配的测试直接推进到s[5]开始的子串。发现s[5]≠t[1]后又排除s[5..10]与t[1..6]完全匹配的可能，从而推进到测试s[6..11]与t[1..6]的完全匹配，得到正确的结果。其中省却了s[5]与t[4]，s[5]与t[3]，s[5]与t[2]的比较。（注意s[5]与t[1]的比较尽管是多余的，但π’[4]=0且s[5]=t[1],按照修改后的KMP算法，还得做s[5]与t[1]的多余比较。）
结论：对KMP的改进实际上是KMP对朴素算法改进的继续，即充分利用部分匹配的信息，不仅充分利用s[k+1..i]=t[1..j]（挖掘可能隐含的匹配）而且充分利用s[i+1]≠t[j+1]（挖掘可能隐含的不匹配）。
无双 注释:
优化点:
KMP算法是对朴素算法进行隐藏匹配的优化
KMP改进算法是对KMP算法隐含不匹配的优化
void Modified_Prefix_function(vector<int>& next,const char* t)
{
// char *x, int m, int kmpNext[]) {
int t_len = strlen(t);
next.swap(vector<int>(t_len+1,0)); // 调整next数组,因为next数组从第二个元素开始使用, 长度为strlen(t)+1
int j = next[0] = -1;
for(int i =0;i < t_len; ){
// 与传统KMP算法不同就是: 如果下一个是=第一个, 那当前的值-1
// 而匹配时, 无论哪一步都会++
while ( j > -1 && t[i] != t[j] ){
printf("j[%d] > -1 && t[%d]:%c != t[%d]:%c next[%d]:%d\n",j,i,t[i],j,t[j],j,next[j]);
j = next[j];
}
i++;
j++;
next[i] = t[i] == t[j]?next[j]:j;
printf("next[%d] = %c == %c ?next[%d]:%d:%d;\n",i,t[i],t[j],j,next[j],j);
}
}
static void Modified_KMP_Matcher(const char* s,const char* t)
{
vector<int> next;
Modified_Prefix_function(next,t);
{
printf("next:\n\t");
for(int i =0;i<next.size();i++){
printf("% 2d ",next[i]);
}
printf("\n");
}
int s_len = strlen(s);
int t_len = strlen(t);
int next_idx=0;
for( int i =0; i< s_len; i++ ){
while( next_idx>-1 && s[i] != t[next_idx] )
next_idx = next[next_idx];
next_idx ++;
if( next_idx >= t_len ){
printf("Mod_KMP_Matcher:S[%s]\tT[%s] pos[%d]\n",s,t,i - t_len+1);
next_idx = next[next_idx];
}
}
}