高效率求子串
字符串str，求str中子串sub的第一次的起始位置：我知道一个很笨的方法，指向str的指针每次向后移一个字符，然后搜索一次是否含有子串sub，如果没有，再向后移一个位置，再搜索，但这个方法效率太低，高效率的怎么写呢？
[解决办法]
#include <iostream>
#include <stdio.h>
using namespace std;
int subString(const char* str, const char* sub) {
assert(NULL != str && NULL != sub);
const char* pStr= NULL;
const char* pSub= NULL;
int index = -1; // 为-1,说明没找到
int backSize = 0;
int tempBackSize = 0; // 退出的步数小于backSize时，还是要后退，但不能用backSize. aabaaaab, aaaab，
// 第一次退1个位置，但backSize却是3个位置，所以要用这个变量来记录。
pSub = sub;
while (( '\0 ' != *pSub) && (*pSub == *(pSub + 1))) {
pSub++;
backSize++;
}
cout < < "Back size : " < < backSize < < endl; // 字串中初始重复的字符数-1, aaaab为3
pStr = str; // aabaaaaab ,aaaab
while ( '\0 ' != *pStr) {
pSub = sub;
if (*pStr == *pSub) { // 如果两个字符串的首字符相同，则进行进一步的搜索
while ((*pStr == *pSub) && (*pStr != '\0 ') && (*pSub != '\0 ')) { // 以防子串长度大于str
pStr++;
pSub++;
tempBackSize++; // 记录有几个字符重复了aabaaaaaab, aaaab,有两个重复，但此时只能后退一步
}
if ( '\0 ' == *pSub) { // 找到子串了
index = pStr - str - strlen(sub);
// 如: 此时位置为aabaaaaaab., aaaab.，而要的位置却是aabaa.aaaab
//pStr = pStr - backSize; // 打开pStr = pStr - backSize; 去掉break;搜索最后一个子串
break; // 打开break;去掉pStr =pStr - backSize;搜索第一个子串
} else if (tempBackSize > 1) { // 当有重复两个或两个以上时才后退.一个时不后退，因为其最小为1.
if (tempBackSize <= backSize) {
// 当重复的字符数少于等于子串的重复字符数，
// 如: aabaaaaaab, aaaab,有两个重复，但此时只能后退一步
// 如重复2步，进入死循环
pStr = pStr - tempBackSize + 1;
tempBackSize = 0;
} else {
tempBackSize = 0;
pStr = pStr - backSize;
}
}
} else {
pStr++;
}
}
return index;
}
int main() {
cout < < "Input string : " < < endl;
char str[80];
cin.getline(str, 80);
cout < < "Input SubString : " < < endl;
char sub[80];
cin.getline(sub, 80);
cout < < subString(str, sub) < < endl;
return 0;
}
[解决办法]
【Ref】
模式匹配的KMP算法详解
这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较
难理解的算法，今天特把它搞个彻彻底底明明白白。
注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：
int Index(String S,String T,int pos)//参考《数据结构》中的程序
{
i=pos;j=1;//这里的串的第1个元素下标是1
while(i <=S.Length && j <=T.Length)
{
if(S[i]==T[j]){++i;++j;}
else{i=i-j+2;j=1;}//**************(1)
}
if(j> T.Length) return i-T.Length;//匹配成功
else return 0;
}
匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子：
S:aaaaabababcaaa T:ababc
aaaaabababcaaa
ababc.(.表示前一个已经失配)
回溯的结果就是
aaaaabababcaaa
a.(babc)
如果不回溯就是
aaaaabababcaaa
aba.bc
这样就漏了一个可能匹配成功的情况
aaaaabababcaaa
ababc
为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后 '部分匹配 '的性质。如果T为abcdef这样的，大没
有回溯的必要。
改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。
如果不用回溯，那T串下一个位置从哪里开始呢？
还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：
...ababd...
ababc
-> ababc
这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值
，它是由T串本身固有决定的，与S串无关。
《数据结构》上给了next值的定义：
0 如果j=1
next[j]={Max{k|1 <k <j且 'p1...pk-1 '= 'pj-k+1...pj-1 '
1 其它情况
我当初看到这个头就晕了，其实它就是描述的我前面表述的情况，关于next[1]=0是规定的，这样规定可以使程序简单一些，如果
非要定为其它的值只要不和后面的值冲突也是可以的；而那个Max是什么意思，举个例子：
T:aaab
...aaaab...
aaab
-> aaab
-> aaab
-> aaab
像这样的T，前面自身部分匹配的部分不止两个，那应该往前跳到第几个呢？最近的一个，也就是说尽可能的向右滑移最短的长度
。
OK，了解到这里，就看清了KMP的大部分内容，然后关键的问题是如何求next值？先不管它，先看如何用它来进行匹配操作，也就
是说先假设已经有了next值。
将最前面的程序改写成：
int Index_KMP(String S,String T,int pos)
{
i=pos;j=1;//这里的串的第1个元素下标是1
while(i <=S.Length && j <=T.Length)
{
if(j==0 || S[i]==T[j]){++i;++j;} //注意到这里的j==0,和++j的作用就知道为什么规定next[1]=0的好处了
else j=next[j];//i不变（不回溯）,j跳动
}
if(j> T.Length) return i-T.Length;//匹配成功
else return 0;
}
OK,是不是非常简单？还有更简单的，求next值，这也是整个算法成功的关键，从next值的定义来求太恐怖了，怎么求？前面说过
了，next值表达的就是T串的自身部分匹配的性质，那么，我只要将T串和T串自身来一次匹配就可以求出来了，这里的匹配过程不
是从头一个一个匹配，而是从T[1]和T[2]开始匹配，给出算法如下：
void get_next(String T,int &next[])
{
i=1;j=0;next[1]=0;
while(i <=T.Length)
{
if(j==0 || T[i]==T[j]){++i;++j; next[i]=j;/**********(2)*/}
else j=next[j];
}
}
看这个函数是不是非常像KMP匹配的函数，没错，它就是这么干的！注意到(2)语句逻辑覆盖的时候是T[i]==T[j]以及i前面的、j
前面的都匹配的情况下，于是先自增，然后记下来next[i]=j，这样每当i有自增就会求得一个next[i]，而j一定会小于等于i，于
是对于已经求出来的next，可以继续求后面的next，而next[1]=0是已知，所以整个就这样递推的求出来了，方法非常巧妙。
这样的改进已经是很不错了，但算法还可以改进，注意到下面的匹配情况：
...aaac...
aaaa.
T串中的 'a '和S串中的 'c '失配，而 'a '的next值指的还是 'a '，那同样的比较还是会失配，而这样的比较是多余的，如果我事先知
道，当T[i]==T[j]，那next[i]就设为next[j]，在求next值的时候就已经比较了，这样就可以去掉这样的多余的比较。于是稍加
改进得到：
void get_nextval(String T,int &next[])
{
i=1;j=0;next[1]=0;
while(i <=T.Length)
{
if(j==0 || T[i]==T[j])
{ ++i;++j;
if(T[i]!=T[j]) next[i]=j;
else next[i]=next[j];//消去多余的可能的比较,next再向前跳
}
else j=next[j];
}
}
匹配算法不变。
