字符串匹配的算法当属KMP最为著名了，人人皆知，但是KMP算法是如何做到高效率字符串匹配的呢？
我们首先来看看一般的暴力的字符串匹配算法，对于串s和模式串pattern，依次枚举s中的每一个字符作为起点与pattern尝试进行匹配，直到遇到不匹配的字符的时候，取下一个s中的字符作为起点与模式串pattern重新进行匹配。我们知道这样的时间复杂度是O(n*m)的，显然效率很不好。
从上面暴力匹配的过程我们可以知道，当暴力进行匹配的时候，遇到不匹配的字符，不一定要从s的下一个字符重新与模式串进行匹配，那么我们如何做到这一点呢？这就要用到KMP中神奇的next数组了。
next数组记录的是模式串的特征，从而当匹配不成功的时候，我们不一定完全对s的下一个字符与模式串从头开始匹配。于是next[i]表示当i与s中的某个串匹配不成功的时候，我们应该用第next[i]的字符与s中的当前位进行匹配。也就是说模式串pattern的子串[pattern[0], pattern[next[k]-1]]与子串[pattern[k-next[k]], pattern[k-1]]完全相同。
我们为什么能将next数组用在与s的匹配过程中呢？因为当s[i]与patter[k]不匹配的时候，说明pattern的子串[pattern[0], pattern[k-1]]已经与s的子串[s[i-k], s[i-1]]完全匹配了，而这个时候借助next数组，我们知道如果pattern有一个前缀与s[0, i-1]的某一个后缀完全相同，我们就应该将前缀的最后一个字符的后面一个字符同s[i]进行尝试匹配。这样子大大的减少了没有作用的盲目匹配尝试。
我们可以预见KMP算法的均摊复杂度是O(n+m)，为什么呢？因为你的s串是不会回退的，因此最多访问了n次，而模式串pattern在每一次匹配中的走动均摊下来近似为O(m)的，因此总的复杂度为O(n+m)。
下面贴上我的KMP算法的模板，如果模式串在s中出现，则返回子串第一次出现的位置，否则返回-1。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
const int kMax1 = 1000010;
const int kMax2 = 10010;
char g_pattern[kMax2];
char g_s[kMax1];
int g_next[kMax2];
void GetNext(int n)
{
memset(g_next, -1, sizeof(g_next));
g_next[0] = -1;
g_next[1] = 0;
int k = 0;
int i = 1;
while(i<(n-1))
{
//printf("i=%d, k=%d\n", i, k);
if(k == -1 || g_pattern[k] == g_pattern[i])
{
++i; ++k;
g_next[i] = k;
}
else
k = g_next[k];
}
}
int KMP(int n)
{
int ans = -1;
int i = 0;
int j = 0;
int pattern_len = strlen(g_pattern);
while(i < n)
{
if(j == -1 || g_s[i] == g_pattern[j])
{
++i; ++j;
}
else
j = g_next[j];
if(j == pattern_len)
{
ans = i - pattern_len;
}
}
return ans;
}
该篇博文关于KMP算法的理解和代码，都是自己参照数据结构与算法的书上面的一点理解。而代码之前自己写的方式不一样，为了规范和容易阅读，参考了网上的代码，这个代码肯定是没有问题的，初学者可以放心的拿去当做模板使用。
最后如果牛人发现了本博文存在纰漏，望牛人不吝赐教，我定当认真改过。
中介者模式将一个网状的系统结构变成一个以中介者对象为中心的星形结构，在这个星型结构中，使用中介者对象与其他对象的一对多关系来取代原有对象之间的多对多关系。中介者模式在事件驱动类软件中应用较为广泛，特别是基于GUI（Graphical User Interface，图形用户界面）的应用软件，此外，在类与类之间存在错综复杂的关联关系的系统中，中介者模式都能得到较好的应用。
1. 主要优点
中介者模式的主要优点如下：
(1) 中介者模式简化了对象之间的交互，它用中介者和同事的一对多交互代替了原来同事之间的多对多交互，一对多关系更容易理解、维护和扩展，将原本难以理解的网状结构转换成相对简单的星型结构。
(2) 中介者模式可将各同事对象解耦。中介者有利于各同事之间的松耦合，我们可以独立的改变和复用每一个同事和中介者，增加新的中介者和新的同事类都比较方便，更好地符合“开闭原则”。
(3) 可以减少子类生成，中介者将原本分布于多个对象间的行为集中在一起，改变这些行为只需生成新的中介者子类即可，这使各个同事类可被重用，无须对同事类进行扩展。
2. 主要缺点
中介者模式的主要缺点如下：
在具体中介者类中包含了大量同事之间的交互细节，可能会导致具体中介者类非常复杂，使得系统难以维护。
3. 适用场景
在以下情况下可以考虑使用中介者模式：
(1) 系统中对象之间存在复杂的引用关系，系统结构混乱且难以理解。
(2) 一个对象由于引用了其他很多对象并且直接和这些对象通信，导致难以复用该对象。
(3) 想通过一个中间类来封装多个类中的行为，而又不想生成太多的子类。可以通过引入中介者类来实现，在中介者中定义对象交互的公共行为，如果需要改变行为则可以增加新的具体中介者类。
练习
Sunny软件公司欲开发一套图形界面类库。该类库需要包含若干预定义的窗格(Pane)对象，例如TextPane、ListPane、GraphicPane等，窗格之间不允许直接引用。基于该类库的应用由一个包含一组窗格的窗口(Window)组成，窗口需要协调窗格之间的行为。试采用中介者模式设计该系统。
2010年上半年 软件设计师 下午试卷 第三题
【说明】
某运输公司决定为新的售票机开发车票销售的控制软件。图I给出了售票机的面板示意图以及相关的控制部件。
图I 售票机面板示意图
售票机相关部件的作用如下所述：
(1) 目的地键盘用来输入行程目的地的代码（例如，200表示总站）。
(2) 乘客可以通过车票键盘选择车票种类（单程票、多次往返票和座席种类）。
(3) 继续/取消键盘上的取消按钮用于取消购票过程，继续按钮允许乘客连续购买多张票。
(4) 显示屏显示所有的系统输出和用户提示信息。
(5) 插卡口接受MCard（现金卡），硬币口和纸币槽接受现金。
(6) 打印机用于输出车票。
(7) 所有部件均可实现自检并恢复到初始状态。
现采用面向对象方法开发该系统，使用UML进行建模，系统的顶层用例图和类图分别如图II和图III所示。
图II 顶层用例图
图III 类图
【问题1】
根据说明中的描述，给出图II中A1和A2所对应的执行者，U1所对应的用例，以及(1)、(2)处所对应的关系。
【问题2】
根据说明中的描述，给出图III中缺少的C1-C4所对应的类名以及(3)-(6)处所对应的多重度。
【问题3】
图III中的类图设计采用了中介者(Mediator)设计模式，请说明该模式的内涵。
经验总结：
联机日志分为当前联机日志和非当前联机日志，非当前联机日志的损坏是比较简单的，一般通过clear命令就可以解决问题。
损坏非当前联机日志：
1、启动数据库，遇到ORA-00312 or ORA-00313错误，如:
ORA-00313: open failed for members of log group 4 of thread 1
ORA-00312: online log 3 thread 1: '/opt/oracle/db04/oradata/ORCL/redo03.log'
从这里我们知道日志组1的数据文件损坏或丢失了
从报警文件可以看到更详细的信息
2、查看V$log视图:
SQL>; select group#,sequence#,archived,status from v$log;
GROUP# SEQUENCE# ARC STATUS
---------- ---------- --- ----------------
1 54 YES INACTIVE
2 55 NO CURRENT
3 53 YES INACTIVE
可以知道，该组是非当前状态，而且已经归档。
3、用CLEAR命令重建该日志文件
SQL>;alter database clear logfile group 3;
如果是该日志组还没有归档，则需要用
SQL>;alter database clear unarchived logfile group 3;
4、打开数据库，重新备份数据库
SQL>;alter database open;
说明：
1)、如果损坏的是非当前的联机日志文件，一般只需要clear就可以重建该日志文件，但是如果该数据库处于归档状态但该日志还没有归档，就
需要强行clear。
2)、建议clear，特别是强行clear后作一次数据库的全备份。
3)、此方法适用于归档与非归档数据库。
损坏当前联机日志：
归档模式下当前日志的损坏有两种情况，
一、是数据库是正常关闭，日志文件中没有未决的事务需要实例恢复，当前日志组的损坏就可以直接用alter database clear unarchived
logfile group n来重建。
二、是日志组中有活动的事务，数据库需要媒体恢复，日志组需要用来同步，有两种补救办法
A. 最好的办法就是通过不完全恢复，可以保证数据库的一致性，但是这种办法要求在归档方式下，并且有可用的备份
B. 通过强制性恢复，但是可能导致数据库不一致。
下面分别用来说明这两种恢复方法
5.1.2.1 通过备份来恢复
1、打开数据库，会遇到一个类似的错误
ORA-00313: open failed for members of log group 1 of thread 1
ORA-00312: online log 1 thread 1: 'D:\ORACLE\ORADATA\TEST\REDO01.LOG'
ORA-27041: unable to open file
OSD-04002: unable to open file
O/S-Error: (OS 2) 系统找不到指定的文件
2、查看V$log，发现是当前日志
SQL>; select group#,sequence#,archived,status from v$log;
GROUP# SEQUENCE# ARCHIVED STATUS
---------- ---------- -------- ----------------
1 1 NO CURRENT
2 2
YES INACTIVE
3 3 YES INACTIVE
3、发现clear不成功
SQL>; alter database clear unarchived logfile group 1;
alter database clear unarchived logfile group 1
*
ERROR at line 1:
ORA-01624: log 1 needed for crash recovery of thread 1
ORA-00312: online log 1 thread 1: 'D:\ORACLE\ORADATA\TEST\REDO01.LOG'
4、拷贝有效的数据库的全备份，并不完全恢复数据库
可以采用获取最近的SCN的办法用until scn恢复或用until cnacel恢复
recover database until cancel
先选择auto，尽量恢复可以利用的归档日志，然后重新
recover database until cancel
这次输入cancel，完成不完全恢复，也就是说恢复两次。
如：
SQL>; recover database until cancel;
Auto
……
SQL>; recover database until cancel;
Cancel;
5、利用alter database open resetlogs打开数据库
说明：
1、这种办法恢复的数据库是一致的不完全恢复，会丢失当前联机日志中的事务数据
2、这种方法适合于归档数据库并且有可用的数据库全备份。
3、恢复成功之后，记得再做一次数据库的全备份。
4、建议联机日志文件一定要实现镜相在不同的磁盘上，避免这种情况的发生，因为任何数据的丢失对于生产来说都是不容许的。
如果没有备份，进行强制性恢复
1、打开数据库，会遇到一个类似的错误
ORA-00313: open failed for members of log group 1 of thread 1
ORA-00312: online log 1 thread 1: 'D:\ORACLE\ORADATA\TEST\REDO01.LOG'
ORA-27041: unable to open file
OSD-04002: unable to open file
O/S-Error: (OS 2) 系统找不到指定的文件
2、查看V$log，发现是当前日志
SQL>; select group#,sequence#,archived,status from v$log;
GROUP# SEQUENCE# ARCHIVED STATUS
---------- ---------- -------- ----------------
1 1 NO CURRENT
2 2 YES INACTIVE
3 3 YES INACTIVE
3、发现clear不成功
SQL>; alter database clear unarchived logfile group 1;
alter database clear unarchived logfile group 1
*
ERROR at line 1:
ORA-01624: log 1 needed for crash recovery of thread 1
ORA-00312: online log 1 thread 1: 'D:\ORACLE\ORADATA\TEST\REDO01.LOG'
4、把数据库down掉
SQL>;shutdown immediate
5、在init<sid>;.ora中加入如下参数
_allow_resetlogs_corruption=TRUE
6、重新启动数据库,利用until cancel恢复
SQL>;recover database until cancel;
Cancel
如果出错，不再理会，发出
SQL>;alter database open resetlogs;
7、数据库被打开后，马上执行一个full export
8、shutdown数据库,去掉_all_resetlogs_corrupt参数
9、重建库
10、import并完成恢复
11、建议执行一下ANALYZE TABLE ...VALIDATE STRUCTURE CASCADE;
说明：
1、该恢复方法是没有办法之后的恢复方法，一般情况下建议不要采用，因为该方法可能导致数据库的不一致
2、该方法也丢失数据，但是丢失的数据没有上一种方法的数据多，主要是未写入数据文件的已提交或未提交数据。
3、建议成功后严格执行以上的7到11步，完成数据库的检查与分析
4、全部完成后做一次数据库的全备份
5、建议联机日志文件一定要实现镜相在不同的磁盘上，避免这种情况的发生，因为任何数据的丢失对于生产来说都是不容许的。