摘要:首先在 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];
}
}
}
模式匹配及其五种求解算法
刘怡安
归纳整理
一、模式匹配问题的提法
所谓模式匹配是在给定的、称为主串的字符串S[1..n]中寻找与给定的另一个称为模式(串)的字符串T[1..m]完全匹配的所有子串的位置,即寻找非负整数集
P={k|0≤k≤n-m,S[k+1..k+m]=T[1..m]}。……………………………………(1.1)
如S[1..13]=’ababcabcacbab’,T[1..5]=’abcac’,则答案是P=
{5}。这里假设S[1..n]和
T[1..m]中的字符来自字符集∑,比如{0,1}或{a,b,…,z}或ASCII字符集等。集合(1.1)中的k实际上不是S的子串S[k+1..
k+m]的位置,因为S[k+1..k+m]的位置定义为k+1。但是,k唯一地确定了S[k+1..k+m]的位置,而且用它作参数,表达式更直观,所
以,我们把k而不是把k+1作为问题的直接求解对象,因而下文不妨就称k为位置。
二、模式匹配问题的应用背景
在计算机上用编辑程序作文本编辑时,用户常常要在一个文本中寻找一个给定字符串(模式串)的所有出现。这就是一个模式匹配问题。解决这个问题的效率直接反映出编辑程序的响应速度,从而反应出编辑程序的优劣。在其他应用领域,如在DNA序列中寻找特殊的模式,也要用到模式匹配。
三、模式匹配问题的一簇算法
由于模式匹配问题的求解效率的重要性,对模式匹配算法的研究很早就受到重视,因而积累了丰富的成果。这里要介绍其中脉络清晰的五种算法,它们依次是朴素匹配,KMP匹配,KMP匹配的改进,Boyer-Moore匹配,和Rabin-Karp匹配。
(一) 模式匹配的朴素算法
模式匹配一个马上可以给出的算法是:将S
和T分别存放在字符数组S[1..n]和T[1..m]中,然后从左到右逐个地检查S中可能与T[1..m]完全匹配的每一个子串S[I+1..i+
m],其中i=0,1,2,…,n-m。如果在S[1..n]中找不到与T[1..m]完全匹配的子串,则模式匹配问题无解。这个算法称为朴素的模式匹配
算法,有Naive_Matcher来标识。它容易表述如下:
Proc. Naive_Matcher (s, t:string);
var m, n, j,k:integer;
begin
(1) n:=Length (s);
(2) m:=Length (t); {n≥m}
(3) for k:=0 to n-m do
begin
(4) for j:=1 to m do {注意:这里检测s[k+1..k+m]与t[1..m]的完全匹配性是从左到右逐个字符进行的}
(5) if s[k+j]≠t[j] then goto L;
(6) print (k); {找到匹配位置k}
(7) L:end;
end;{Naive-Matcher}
c代码如下:[无双添加,从上面的pascal转换而来]
//算法原理: 对于s, 从每一个位置开始进行匹配, 看看是不是可以整个匹配 如果可以 那会打印出下标
static void Naive_Matcher(const char* s,const char* t)
{
int n = strlen(s);
int m = strlen(t);
if(n<m)
return ;
for(int k = 0;k<=(n-m);k++){ //从s串中每一个下标开始
for(int j = 0;j<m;j++ )//试图进行t串的全匹配
if( s[k+j] != t[j] ) //如果不成功进跳出
goto L;
printf("S[%s] T[%s]:%d\n",s,t,k); //如果全部成功打印坐标
L:;
}
return ;
}
int main()
{
Naive_Matcher("abcd","ab");
Naive_Matcher("abcd","bc");
Naive_Matcher("abcd","cd");
Naive_Matcher("abcd","de");
Naive_Matcher("abcd","bd");
Naive_Matcher("abcdebcfcef","bc");
return 0;
}

很明显,这个算法需要的时间主要花在关于k 和j的二重for循环上,所以,其时间复杂性T(m ,n)=O((n-m+1)·m)= O(m·n)。另外,对于特殊的输入s =’aa…aa’ 和t=’aa…ab’,又需要θ(m·n)的时间,故在最坏情况下T(m,n)=θ(m·n)。 n m
摘要:
模式匹配及其五种求解算法
刘怡安
归纳整理
此处阅读全文
2006年03月20日
旧的, 用于vim63的
set nocompatible
source $VIMRUNTIME/vimrc_example.vim
source $VIMRUNTIME/mswin.vim
behave xterm
set ffs=unix,dos
set langmenu=none
language C
set diffexpr=MyDiff()
function MyDiff()
let opt = '-a --binary '
if &diffopt =~ 'icase' | let opt = opt . '-i ' | endif
if &diffopt =~ 'iwhite' | let opt = opt . '-b ' | endif
let arg1 = v:fname_in
if arg1 =~ ' ' | let arg1 = '"' . arg1 . '"' | endif
let arg2 = v:fname_new
if arg2 =~ ' ' | let arg2 = '"' . arg2 . '"' | endif
let arg3 = v:fname_out
if arg3 =~ ' ' | let arg3 = '"' . arg3 . '"' | endif
silent execute '!D:\tools\gnu\Vim\vim63\diff ' . opt . arg1 . ' ' . arg2 . ' > ' . arg3
endfunction
hi HL_HiCurLine ctermfg=blue ctermbg=cyan guifg=blue guibg=cyan
let HL_HiCurLine= "HL_HiCurLine"
set formatoptions=tcrqn2
set guifont=FixedsysTTF:h14 "如果没有这个字体那就不要加
set guioptions-=T
set tabstop=8
set softtabstop=4
set shiftwidth=4
colorscheme desert "ps_color
"在gvim下可以看到有多少coloscheme
set lsp=0
set sw=4 " shiftwidth
set et " expandtab
"set wm=8 " wrapmargin
set bs=2 " backspace
set ru " ruler
set ic " ignorecase "忽略大小写 但是输入中有大写的话不忽略
set is " incsearch
set scs " smartcase: override the 'ic' when searching
" if search pattern contains uppercase char
set wmnu
set wildignore=*.bak,*.o,*.e,*~
iab #i #include
iab #d #define
iab #e #endif
set cst
set csto=1
"D:\tools\dev\Microsoft Visual Studio\VC98\MFC\Include\tags
"D:\tools\dev\Microsoft Visual Studio\VC98\Include\tags
"C:\Symbian\UIQ_21\epoc32\include\tags
set tags=./tags,../tags,../../tags,../../../tags,D:/tools/dev/Microsoft\ Visual\ Studio/VC98/Include/tags
set cspc=3 " show file path's last three part
set grepprg=grep\ -nH
map <F1> :Tlist<cr>
map <F2> :WMToggle<cr>
map <F3> zO
map <F4> zc
map <F5> zR
map <F6> zM
map <F7> :cn<CR>
"
set vb t_vb= " set visual bell and disable screen flash
set backup " enable backup and define the backup file
set backupext=.bak
set hlsearch " hlsearch
" allow backspacing over everything in
" the insert mode
set backspace=indent,eol,start
set dir=D:\tmp\vim
" 设置swap文件的目录上面
set backupdir=D:\tmp\vim
"设置备份文件的目录上面 我不喜欢看到每个目录下都有备份 因为一般备份用不到
"下面是设置自动folder的 而且是根据写C代码设置的 如果你不喜欢使用folder那么可以省略掉
"au BufReadPost *.h,*.c,*.cpp,*.java,*.pl syn region myFold start="{" end="}" transparent fold
"au BufReadPost *.h,*.c,*.cpp,*.java,*.pl syn sync fromstart
"au BufReadPost *.h,*.c,*.cpp,*.java,*.pl set foldmethod=syntax
"set foldlevel=0
"set foldmarker={,}
set foldmethod=syntax "marker
set foldlevel=100 " Don't autofold anything (but I can still fold manually)
set foldopen-=search " don't open folds when you search into them
set foldopen-=undo " don't open folds when you undo stuff
"-------------------------------------------------------------------------------
" C-support.vim
"-------------------------------------------------------------------------------
let g:C_AuthorName = 'Zhonglei Li'
let g:C_AuthorRef = ''
let g:C_Email = 'Zhonglei_Li@trendmicro.com.cn'
let g:C_Company = 'Trend Micro Incorporated'
"-------------------------------------------------------------------------------
" copy from web
"-------------------------------------------------------------------------------
set history=1000 " How many lines of history to remember
set cf " enable error files and error jumping
set clipboard+=unnamed " turns out I do like is sharing windows clipboard
filetype plugin on " load filetype plugins
set viminfo+=! " make sure it can save viminfo
set isk+=_,$,@,%,#,- " none of these should be word dividers, so make them not be
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Vim UI
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
set lsp=0 " space it out a little more (easier to read)
set wildmenu " turn on wild menu
set ruler " Always show current positions along the bottom
set cmdheight=1 " the command bar is 2 high
"set number " turn on line numbers
set lz " do not redraw while running macros (much faster) (LazyRedraw)
"set hid " you can change buffer without saving
set backspace=2 " make backspace work normal
set whichwrap+=<,>,h,l " backspace and cursor keys wrap to
set mouse=a " use mouse everywhere
set shortmess=atI " shortens messages to avoid 'press a key' prompt
set report=0 " tell us when anything is changed via :...
set noerrorbells " don't make noise
" make the splitters between windows be blank
set fillchars=vert:\ ,stl:\ ,stlnc:\
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Visual Cues
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
"set showmatch " show matching brackets
"set mat=5 " how many tenths of a second to blink matching brackets for
"set nohlsearch " do not highlight searched for phrases
set incsearch " BUT do highlight as you type you search phrase
set listchars=tab:\|\ ,trail:.,extends:>,precedes:<,eol:$ " what to show when I hit :set list
set lines=80 " 80 lines tall
set columns=160 " 160 cols wide
set so=0 " Keep 10 lines (top/bottom) for scope
set novisualbell " don't blink
set noerrorbells " no noises
set statusline=%F%m%r%h%w\ [FORMAT=%{&ff}]\ [TYPE=%Y]\ [ASCII=\%03.3b]\ [HEX=\%02.2B]\ [POS=%04l,%04v][%p%%]\ [LEN=%L]
set laststatus=2 " always show the status line
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Text Formatting/Layout
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
set fo=tcrqn " See Help (complex)
"set ai " autoindent
"set si " smartindent
"set cindent " do c-style indenting
"set tabstop=8 " tab spacing (settings below are just to unify it)
"set softtabstop=8 " unify
"set shiftwidth=8 " unify
"set noexpandtab " real tabs please!
"set nowrap " do not wrap lines
"set smarttab " use tabs at the start of a line, spaces elsewhere
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Folding
" Enable folding, but by default make it act like folding is off, because folding is annoying in anything but a few rare cases
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
"set foldenable " Turn on folding
"set foldmethod=indent " Make folding indent sensitive
"set foldlevel=100 " Don't autofold anything (but I can still fold manually)
"set foldopen-=search " don't open folds when you search into them
"set foldopen-=undo " don't open folds when you undo stuff
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" File Explorer
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
let g:explVertical=1 " should I split verticially
let g:explWinSize=20 " width of 35 pixels
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Win Manager
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
let g:winManagerWidth=20 " How wide should it be( pixels)
let g:winManagerWindowLayout = 'FileExplorer,TagsExplorer|BufExplorer' " What windows should it
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" CTags
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
"let Tlist_Ctags_Cmd = $VIM.'\ctags.exe' " Location of ctags
let Tlist_Sort_Type = "name" " order by
"let Tlist_Use_Right_Window = 1 " split to the right side of the screen
let Tlist_Compart_Format = 1 " show small meny
let Tlist_Exist_OnlyWindow = 1 " if you are the last, kill yourself
let Tlist_File_Fold_Auto_Close = 0 " Do not close tags for other files
let Tlist_Enable_Fold_Column = 0 " Do not show folding tree
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Minibuf
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
"let g:miniBufExplTabWrap = 1 " make tabs show complete (no broken on two lines)
"let g:miniBufExplModSelTarget = 1
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Matchit
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
let b:match_ignorecase = 1
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Perl
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
let perl_extended_vars=1 " highlight advanced perl vars inside strings
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Custom Functions
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Select range, then hit :SuperRetab($width) - by p0g and FallingCow
function! SuperRetab(width) range
silent! exe a:firstline . ',' . a:lastline . 's/\v%(^ *)@<= {'. a:width .'}/\t/g'
endfunction
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Mappings
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
"map <right> <ESC>:MBEbn<RETURN> " right arrow (normal mode) switches buffers (excluding minibuf)
"map <left> <ESC>:MBEbp<RETURN> " left arrow (normal mode) switches buffers (excluding minibuf)
"map <up> <ESC>:Sex<RETURN><ESC><C-W><C-W> " up arrow (normal mode) brings up a file list
"map <down> <ESC>:Tlist<RETURN> " down arrow (normal mode) brings up the tag list
"map <A-i> i <ESC>r " alt-i (normal mode) inserts a single char, and then switches back to normal
"map <F2> <ESC>ggVG:call SuperRetab()<left>
"map <F12> ggVGg? " encypt the file (toggle)
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Autocommands
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
"autocmd BufEnter * :syntax sync fromstart " ensure every file does syntax highlighting (full)
"au BufNewFile,BufRead *.asp :set ft=aspjscript " all my .asp files ARE jscript
"au BufNewFile,BufRead *.tpl :set ft=html " all my .tpl files ARE html
"au BufNewFile,BufRead *.hta :set ft=html " all my .tpl files ARE html
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Useful abbrevs
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
"iab xasp <%@language=jscript%><CR><%<CR><TAB><CR><BS>%><ESC><<O<TAB>
"iab xdate <c-r>=strftime("%d/%m/%y %H:%M:%S")<cr>
新的 用于vim70的,简化了很多选项 另外使用Bitstream_Vera_Sans_Mono字体, 因为我发现它看起来比较好看
设置字体的方法:
打开gvim,然后在菜单中选择字体与大小
选择好了后, 在命令模式下输入
set guifont
vim会显示出当前使用的字体 把这个字体抄下来保存到 vimrc就可以
set nocompatible
source $VIMRUNTIME/vimrc_example.vim
source $VIMRUNTIME/mswin.vim "跟平台相关,如果不是ms平台去掉
behave xterm
set ffs=unix,dos
set langmenu=none
set wmnu
if (has("gui_running"))
set guifont=Bitstream_Vera_Sans_Mono:h12:cANSI
source $VIMRUNTIME/delmenu.vim
source $VIMRUNTIME/menu.vim
set guioptions-=T " 去掉工具栏,我喜欢显示的范围更大的
endif
colorscheme desert " ps_color
set stal=1 " 当打开多个tab时显示tab,如果只有一个则不显示
set formatoptions=tcrqn2mB
set ts=8 " tab是8空格
set sw=4 "shift width,indent时的值是4格
set sts=4 " soft tab是4空格
set bs=2 " backspace模式
set ru " 显示标尺
set ic " 忽略大小写
set is " 增量查找
set scs " 查找时智能大小写
set lsp=0 " space it out a little more (easier to read)
set wildignore=*.bak,*.o,*.e,*~
iab #i #include
iab #d #define
iab #e #endif
" 设置使用cscope
set cst
set csto=1
set tags=./tags,../tags,../../tags,../../../tags,D:/tools/dev/Microsoft\ Visual\ Studio/VC98/Include/tags
set cspc=3 " show file path's last three part
set grepprg=grep\ -nH
map <F1> :Tlist<cr>
map <F2> :WMToggle<cr>
map <F3> zO
map <F4> zc
map <F5> zR
map <F6> zM
map <F7> :cn<CR>
"
set vb t_vb= " set visual bell and disable screen flash
set backup " enable backup and define the backup file
set backupext=.bak
set hlsearch " hlsearch
" allow backspacing over everything in
" the insert mode
set backspace=indent,eol,start
set dir=D:\tmp\vim
" 设置swap文件的目录上面
set backupdir=D:\tmp\vim
"设置备份文件的目录上面 我不喜欢看到每个目录下都有备份 因为一般备份用不到
set foldmethod=syntax " marker,folder模式为语法
set foldlevel=100 " Don't autofold anything (but I can still fold manually)
set foldopen-=search " don't open folds when you search into them
set foldopen-=undo " don't open folds when you undo stuff
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
" Perl
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
let perl_extended_vars=1 " highlight advanced perl vars inside strings
2006年03月17日
出租司机给我上的MBA课——超强必读(转载)
|
作者:蟹渣渣 提交日期:2006-3-16 16:56:00 |
|
本帖的主题和房版无关,但是文中主人公体现出来的职业水准和乐观的心态令人打心眼的佩服,小蟹转载进来,大家一起看看:-)
=============================================================================
出租司机给我上的MBA课——超强必读-----转帖
http://club.qingdaonews.com/showAnnounce.php?topic_id=3197087&board_id=2&reply_num=3&pic_id=29&tn=1142494422&lr=
我要从徐家汇赶去机场,于是匆匆结束了一个会议,在美罗大厦前搜索出租车。一辆大众发现了我,非常专业的、径直的停在我的面前。这一停,于是有了后面的
这个让我深感震撼的故事,象上了一堂生动的MBA案例课。为了忠实于这名出租车司机的原意,我凭记忆尽量重复他原来的话。
“去哪里……好的,机场。我在徐家汇就喜欢做美罗大厦的生意。这里我只做两个地方。美罗大厦,均瑶大厦。你知道吗?接到你之前,我在美罗大厦门口兜了两圈,终于被我看到你了!从写字楼里出来的,肯定去的不近~~~”
“哦?你很有方法嘛!”我附和了一下。
“做出租车司机,也要用科学的方法。”他说。我一愣,顿时很有些兴趣“什么科学的方法?”
“要懂得统计。我做过精确的计算。我说给你听啊。我每天开17个小时的车,每小时成本34.5元……”
“怎么算出来的?”我追问。
“你算啊,我每天要交380元,油费大概210元左右。一天17小时,平均每小时固定成本22元,交给公司,平均每小时12.5元油费。这是不是就是
34.5
元?”,我有些惊讶。我打了10年的车,第一次听到有出租车司机这么计算成本。以前的司机都和我说,每公里成本0.3元,另外每天交多少钱之类的。
“成本是不能按公里算的,只能按时间算。你看,计价器有一个“检查”功能。你可以看到一天的详细记录。我做过数据分析,每次载客之间的空驶时间平均为7
分钟。如果上来一个起步价,10元,大概要开10分钟。也就是每一个10元的客人要花17分钟的成本,就是9.8元。不赚钱啊!如果说做浦东、杭州、青浦
的客人是吃饭,做10元的客人连吃菜都算不上,只能算是撒了些味精。”
强!这位师傅听上去真不象出租车司机,到象是一位成本核算师。“那你怎么办呢?”我更感兴趣了,继续问。看来去机场的路上还能学到新东西。
“千万不能被客户拉了满街跑。而是通过选择停车的地点,时间,和客户,主动地决定你要去的地方。”我非常惊讶,这听上去很有意思。“有人说做出租车司机
是靠运气吃饭的职业。我以为不是。你要站在客户的位置上,从客户的角度去思考。”这句话听上去很专业,有点象很多商业管理培训老师说的“put
yourself into others' shoes.”
“给你举个例子,医院门口,一个拿着药的,一个拿着脸盆的,你带哪一个。”我想了想,说不知道。
“你要带那个拿脸盆的。一般人病小痛的到医院看一看,拿点药,不一定会去很远的医院。拿着脸盆打车的,那是出院的。住院哪有不死人的?今天二楼的谁死
了,明天三楼又死了一个。从医院出来的人通常会有一种重获新生的感觉,重新认识生命的意义,健康才最重要。那天这个说:走,去青浦。眼睛都不眨一下。你说
他会打车到人民广场,再去做青浦线吗?绝对不会!”
我不由得开始佩服。
“再给你举个例子。那天人
民广场,三个人在前面招手。一个年轻女子,拿着小包,刚买完东西。还有一对青年男女,一看就是逛街的。第三个是个里面穿绒衬衫的,外面羽绒服的男子,拿着
笔记本包。我看一个人只要3秒钟。我毫不犹豫地停在这个男子面前。这个男的上车后说:延安高架、南北高架~~~还没说后面就忍不住问,为什么你毫不犹豫地
开到我面前?前面还有两个人,他们要是想上车,我也不好意思和他们抢。我回答说,中午的时候,还有十几分钟就1点了。那个女孩子是中午溜出来买东西的,估
计公司很近;那对男女是游客,没拿什么东西,不会去很远;你是出去办事的,拿着笔记本包,一看就是公务。而且这个时候出去,估计应该不会近。那个男的就
说,你说对了,去宝山。”
“那些在超市门口,地铁口打车,穿着睡衣的人可能去很远吗?可能去机场吗?机场也不会让她进啊。”
有道理!我越听越有意思。
“很多司机都抱怨,生意不好做啊,油价又涨了啊,都从别人身上找原因。我说,你永远从别人身上找原因,你永远不能提高。从自己身上找找看,问题出在哪
里。”这话听起来好熟,好像是“如果你不能改变世界,就改变你自己”,或者Steven
Corvey的“影响圈和关注圈”的翻版。“有一次,在南丹路一个人拦车,去田林。后来又有一次,一个人在南丹路拦车,还是去田林。我就问了,怎么你们从
南丹路出来的人,很多都是去田林呢?人家说,在南丹路有一个公共汽车总站,我们都是坐公共汽车从浦东到这里,然后搭车去田林的。我恍然大悟。比如你看我们
开过的这条路,没有写字楼,没有酒店,什么都没有,只有公共汽车站,站在这里拦车的多半都是刚下公共汽车的,再选择一条最短路经打车。在这里拦车的客户通
常不会高于15元。”
“所以我说,态度决定一切!”我听十几个总裁讲过这句话,第一次听出租车司机这么说。
“要用科学的方法,统计学来做生意。天天等在地铁站口排队,怎么能赚到钱?每个月就赚500块钱怎么养活老婆孩子?这就是在谋杀啊!慢性谋杀你的全家。
要用知识武装自己。学习知识可以把一个人变成聪明的人,一个聪明的人学习知识可以变成很聪明的人。一个很聪明的人学习知识,可以变成天才。”
“有一次一个人打车去火车站,问怎么走。他说这么这么走。我说慢,上高架,再这么这么走。他说,这就绕远了。我说,没关系,你经常走你有经验,你那么走
50块,你按我的走法,等里程表50块了,我就翻表。你只给50快就好了,多的算我的。按你说的那么走要50分钟,我带你这么走只要25分钟。最后,按我
的路走,多走了4公里,快了25分钟,我只收了50块。乘客很高兴,省了10元钱左右。这4公里对我来说就是1块多钱的油钱。我相当于用1元多钱买了25
分钟。我刚才说了,我一小时的成本34.5块,我多合算啊!”
“在大众公司,一般一个司机3、4千,拿回家。做的好的大概5千左右。顶级的司机大概每月能有7000。全大众2万个司机,大概只有2-3个司机,万里挑一,每月能拿到8000以上。我就是这2-3个人中间的一个。而且很稳定,基本不会大的波动。”
太强了!到此为止,我越来越佩服这个出租车司机。
“我常常说我是一个快乐的车夫。有人说,你是因为赚的钱多,所以当然快乐。我对他们说,你们正好错了。是因为我有快乐、积极的心态,所以赚的钱多。”
说的多好啊!
“要懂得体味工作带给你的美。堵在人民广场的时候,很多司机抱怨,又堵车了!真是倒霉。千万不要这样,用心体会一下这个城市的美,外面有很多漂亮的女孩
子经过,非常现代的高楼大厦,虽然买不起,但是却可以用欣赏的眼光去享受。开车去机场,看着两边的绿色,冬天是白色的,多美啊。再看看里程表,100多
了,就更美了!每一样工作都有她美丽的地方,我们要懂得从工作中体会这种美丽。”
“我10年前是强生公司的总教练。8年前在公司作过三个不同部门的部门经理。后来我不干了,一个月就3、5千块,没意思。就主动来做司机。我愿意做一个快乐的车夫。哈哈哈哈。”
到了机场,我给他留了一张名片,说:“你有没有兴趣这个星期五,到我办公室,给微软的员工讲一讲你怎么开出租车的?你就当打着表,60公里一小时,你讲多久,我就付你多少钱。给我电话。”
我迫不及待的在飞机上记录下他这堂生动的MBA课。
摘要:在windows上安装svn的介绍, svn是一个代替cvs的东东, 现在gcc也开始使用svn来做版本管理工具了
在windows上安装svn有两个办法: 1是使用TortoiseSVN来做服务器和客户端, 然后在TortoiseSVN中通过:file:///drive:/path/to/仓库访问, 这个的麻烦是不是很直观, 并且如果仓库使用bdb格式 并发访问可能会有问题
另一种是安装subvision当服务器, 然后使用TortoiseSVN当客户端, 服务器在后台运行看起来比较正规
但需要自己下载个SVNService 工具才能把svn service当成系统服务 , 不然需要命令行执行
具体svn使用的书可以看网上的
《使用Subversion进行版本控制》
(全文共11068字)——点击
此处阅读全文
2006年03月10日
摘要:修心 (全文共3649字)——点击
此处阅读全文