首先我给你两个串，在A串(长n)中找B串出现的首个位置（长m），
可以十分轻松的想到O(nm)的算法。。
但我们十分愉快友好的发现，有些匹配是多余的。。
然后我们发现
如果
a[] = abbababab b[] = abbb
a[1] = b[1] a[2] = b[2]
a[3] = b[3] a[4]!=b[4]
此时如果从a[2]开始重新枚举真是一种愚蠢的行为。。
如果a[]中包含的第一个b[]串中包含着a[4]（假设起点位于x）
那么，可以得到，a[x...4] = a[1...(4-x+1)];
为何？因为我们已经得到了a[1...3]=b[1...3]
而b[1...3] = a[x...x+2];
所以如果答案是[1,4]中某点x
肯定存在：x <= a[1...4]的最长（后缀==前缀）的后缀的起点
似乎是一个不错的优化
所以我们只要求出每一位的最长的（后缀==前缀）的后缀的起点就行了。。
这个似乎很难求啊。。。我们开一个next[]数组来储存这个；
但我们轻松愉快的发现对于每一位来说：具有最优子结构。。无后效性。。。
PS：接下来的应该可以自己推出。。。
所以我们可以通过next[1...i-1]和a[1....i] 来判断next[i]
如果a[i] == a[ next[i-1] + 1 ]
那么很容易的得到next[i] = next[i-1]+1;
如果不相同。。判断 a[i] = a[ next[next[i-1]] + 1 ](为什么？画图想想)
以此类推
测试题目：http://www.wikioi.com/problem/1204/
细节问题可以自己想想，这儿给出我的代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define MAX 1000001
char a[MAX],b[MAX];
int next[MAX];
int kmp(char *a,char *b)
{
int la = strlen(a+1),lb = strlen(b+1),ans = 0;
for (int i = 2; i <= la; i++)
{
int j = next[i-1];
while(j && a[i]!=a[j+1])
j = next[j];
next[i] = j?j+1:(a[i]==a[1]);
}
for (int i = 1, j =1; j <= lb;)
{
if ( a[i] == b[j] )
{
if ( i >= la )
{
return j-i+1;
ans++;
i = next[i];
}
i++;
j++;
}
else
{
while(i>1 && a[i]!=b[j])
i = next[i-1]+1;
if ( i == 1 )
{
i++;
j++;
}
}
}
return ans;
}
int main()
{
scanf("%s%s",a+1,b+1);
printf("%d\n",kmp(b,a));
return 0;
}