开始是发在公司OA上的，斗胆拿出来跟大家分享，高手莫笑啊，呵呵~
笔试题：
请实现在文件中查找指定字符串的算法？
我想这道题大多数人都会用BR（还是BF我忘了）算法，不错！就是你最先想到算法。
但我这里要讲的是更高级的算法，这是我见过的几种神奇的算法之一，发明这个算法的是
三个人，这个算法的名称就是用他们三位名字的首字母命名——KMP。
我们不妨将问题转化为：
实现下面这个函数，该函数返回子串在目标串（或者叫母串）中的位置，失败返回-1。
代码:
int KMP(const char* pc_str, const char* pc_sub);
先放在这里，把原理弄懂了才好实现，现假定有两个字符串：
PS："S0S1S2S3S4S5........Sn"
PX："X0X1X2....Xm"
并假定m <= n（m > n的话目标串不能包含子串了）
现在要运用你的想象力了，为这两个字符串分别准备两个迭代器i, k，你也可以称它们为下
标或指针，总之知道意思就行了，开始i => S0，j => X0，然后比较PS[ i ]和PX[ j ]（这里就是S0和X0），
不等则将i，也就是目标串迭代器加1，此时就是i => S1， j => X0，如此循环直到PS[ i ]
与PX[ j ]相等为止。
好了，现在终于第一个匹配上了，假定是i => Sk，k是0~n中的某一个，j => X0，也就是Sk与X0相等。
然后就是得寸进尺了，将i加1、j也加1，继续比较，如果运气好，那么"SkSk+1Sk+2......Sk+m" == "X0X1X2....Xm"。
但你可能不总是都那么幸运，假定你比较到Sk+a和Xa时，啪！断了，Sk+a不等于Xa，如果是那个原始的方法
的话（BR or BF），肯定就放弃了，然后将i回溯到Sk+1，一切从头开始。
让我们看看有没有补救的办法，虽然出错了，但"SkSk+1Sk+2......Sk+a-1" == "X0X1X2......Xa-1"①，
这是我们的成果，怎能随意丢弃?或许有些妄想，但如果能继续比较就好了，但Sk+a和Xa
确实是不等啊，怎么办呢？那就让Sk+a和PX串中的其它的比吧，总之i我是不想回溯了，
那究竟和谁比呢？a之后的肯定不行，因为连字符Xa在目标串中还不一定有呢。那就只
有a之前的了，也就是Sk+a和a之前的某个Xb（b < a）比，但这样比的话要有个前提，那
就是"Sk+a-b......Sk+a-3Sk+a-2Sk+a-1" == "X0X1X2......Xb-1"②，仔细想想是不是只有满足这个等式，比
较才能在i不回溯的情况下继续。你看到这里我就假定你想明白了，不然就不要继续了，
再回过头想想。好，再看看这段话开头的那个等式，如果你学过一点点数学，应该知道
如果x+y = x+z，那y = z，同样的，将开头的那个等式左边的串的前面截掉一部分使之变得与
②中的左边一样，为了维持①式仍然成立，则必须右边也要截掉前面一部分，就变成了
"Sk+a-b......Sk+a-3Sk+a-2Sk+a-1" == "Xa-b......Xa-3Xa-2Xa-1"③，好了现在①可以不管了，看②和③，那么
前面所说的要满足的前提，也就是②式，借助于③式，可以变成：
"X0X1X2......Xb-1" == "Xa-b......Xa-3Xa-2Xa-1"④
也就是说，只要PX串中已经比较好的前z个字符与后z个字符相等，也就是④式，就能在i不
回溯的情况下继续比较，这就是KMP算法的核心。
希望到现在你还没晕。。。。。。。。。
字体大小设置比较麻烦，大家将就着看吧==__==!
代码:
int KMPGetNext(const char* pc_str, int n)
{
const int STR_LEN = (NULL == pc_str) ? /
-1 : (int)strlen(pc_str);
const int END = n - 1;
int ret = 0;
int max_len = 0;
if ((NULL == pc_str) || (n < 1)) {
ret = -1;
goto END;
}
if (END >STR_LEN) {
ret = -1;
goto END;
}
for (max_len = END - 1; max_len >= 0; --max_len) {
int i = max_len, j = END;
while ((i >= 0) && (pc_str[i--] == pc_str[j--])) {
}
if (i < 0) {
ret = max_len;
goto END;
}
}
END:
return ret;
}
int KMP(const char* pc_str, const char* pc_sub)
{
const int STR_LEN = (NULL == pc_str) ? /
-1 : (int)strlen(pc_str);
const int SUB_LEN = (NULL == pc_sub) ? /
-1 : (int)strlen(pc_sub);
int ret = 0;
int i = 0, j = 0;
if ((NULL == pc_str) || (NULL == pc_sub)) {
ret = -1;
goto END;
}
if (STR_LEN < SUB_LEN) {
ret = -1;
goto END;
}
for (i = 0, j = 0; /
(i < STR_LEN) && (j < SUB_LEN); /
++i, ++j) {
if ((STR_LEN - i) < (SUB_LEN - j)) {
ret = -1;
break;
}
if (pc_str[ i ] != pc_sub[j]) {
j = KMPGetNext(pc_sub, j);
if (j > 0) {
--i;
}
}
}
if (SUB_LEN == j) {
ret = i - SUB_LEN;
}
END:
return ret;
}