问题：给你两个字符串A和B，问B是否为A的子串（A是否包含B）。比如，字符串A="abcdgo"，字符串B="dgo"，我们就说B是A的子串。
假如，A="abababaababacb"，B="ababacb"，我们来看看KMP是怎么工作的。
我们用两个下标i和j分别表示A和B的当前比较位置，其中A[i-j+1..i]与B[0..j-1]完全匹配。也就是说，i不断增加，随着i的增加j相应地变化，且j满足以A[i-1]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i]和B[j]的关系。
当A[i]=B[j]时，i和j各加一；什么时候j=m（B的长度）了，我们就说B是A的子串，并且可以根据这时的i值算出匹配的位置。
当A[i+1]<>B[j+1]，KMP的策略是调整j的位置 （减小j值为j’+1）使得A[i-j’..i]与B[0..j’]；然后继续检查A[i]和新的B[j]是否相等。
我们看一看当 i = j = 5时的情况：
i = 0 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6
此时，A[5]<>B[5]。我们要把j改成比它小的值j’。j’可能是多少呢？仔细想一下，我们发现，j’必须要使得B[0..j-1]中的头j’个字母和末j’个字母完全相等（这样j变成了j’后才能继续保持i和j的性质）。这个j’当然要越大越好。在这里，B [0..4]="ababa"，头3个字母和末3个字母都是"aba"。当j变为为3后，继续前面比较过程。A[5]恰好和B[3]相等。
i = 0 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6
从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当B[j]不匹配时，新的j最大是多少。P[j]应该是所有满足B[0..P[j]-1]=B[j-P[j]..j-1]的最大值。
再后来，A[6]=B[4]，i和j又各增加1，这时，又出现了A[7]<>B[5]的情况：
i = 0 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7
由于P[5]=3，因此新的j=3：
i = 0 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7
这时，新的j=3仍然不能满足A[i]=B[j]，此时我们再次减小j值，将j再次更新为P[3] = 1：
i = 0 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7
这时，新的j=1仍然不能满足A[i]=B[j]，此时我们再次减小j值，将j再次更新为P[1] = 0：
i = 0 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7
终于，A[7]=B[0]，事实上，有可能j到了0仍然不能满足A[i]=B[j]（比如A[7]="d"时）。因此，当j=0时，需要增加i值，保持j不变，直到出现A[i]=B[j]为止。
ref：http://hi.baidu.com/jzyznoi/blog/item/5080fcd3beae19dea9ec9ab9.html
程序代码
// author: jfo()
////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <vector>
using namespace std;
static vector<int> next;
void pre(const string& s)
{
int i, j;
int len = s.length();
next.clear();
next.push_back(0);
next.push_back(0);
for(i = 2; i <= len; i++) {
for(j = i - 1; i > 0; j–) {
// j is the length of sub string
if(s.substr(0, j) == s.substr(i - j, j)) {
next.push_back(j);
break;
}
}
if(!j)
next.push_back(0);
}
}
// 如果s1不包含s2，返回-1；否则返回s2在s1中第一次出现的下标
int KMP(const string& s1, const string& s2)
{
if(s2.length() > s1.length())
return -1;
pre(s2);
int N = s1.length();
int M = s2.length();
int i = 0, j = 0;
while(i < N && j < M) {
if(s1[i] == s2[j])
i++, j++;
else
!j ? i++ : j = next[j];
}
return j == M ? i - M : -1;
}
int main()
{
string s1 = "abcabde";
string s2 = "abd";
cout << (int)s1.find(s2) << endl;
cout << KMP(s1, s2) << endl;
return 0;
}