from brute force to kmp
终于打算回顾KMP，因为最近July的焦点也在这个地方，所以打算复习。KMP是有点儿难的字符串匹配算法，但是难度带来的是多数情况下效率的提升。
当时学DS的时候，匹配过程是比较理解，回溯求next数组稍微有点儿费解，现在把他陈述以下。
首先由易到难，Brute force算法，朴素的O(mn)匹配算法，注意我们的问题集中在如何找到第一次匹配的母串位置
匹配没到底时，失效了，那么回溯，母串起点++，字串j=0,那么对于母串的offset和子串是一样的，因此可以用两个指针变量，邹博PPT用了三个，变量越多越不好感觉。
int bf(string str, string pat)
{
int i=0,//str startpos
j=0,//pat point
//k=0;//matched str point relative to startpos
while((i+j)<str.size()&&j<pat.size())
{
if(str[i+j]==pat[j])
j++;
else
j=0,i=i+1;
}
if(j>=pat.size())
return i;
else
return -1;
}
这是最朴素的，KMP的基础在于如何利用已经匹配的结果来避免后面回溯的不必要匹配，也就是说，如果串满足一点性质，可以推导出回溯的前k个字符一定是匹配上的？
KMP关键是一个next数组，next[j] 表示失效后，j移动到字串的位置，或者说最长前缀的长度，因为是0-base的缘故，另外KMP比较关键的地方在于匹配已经不是str[i+j]==pat[j]了，而是str[i]==pat[j], 这个
问题之前也忽视掉了，导致怎么都回忆不起KMP的核心算法了，因为KMP就是想使得较长的母串不回溯，因为母串往往较长，对于较大的值减少他的系数往往带来有意义的性能提升。
因此 next[j]: str[0…..j-1]中前缀和后缀匹配的最长前缀(后缀)长度，和子串j回溯到的位置值相等。
next[j]<=j-1,这是定义的，如果能到j的话，每个next都能到j了，没有意义，且next[j]>=0 j>=1, next[j]=-1, j=0, 因为当j=0的时候[0,j-1]之间是没数的因此定义一个-1，同时也是为了避免母串子串第一个字符不等导致的无限循环，
主要是j=next[j]这个语句一定要保证j变小了，否则j=0 如果next[j]=0的话 就死循环了，另外从前向后递推next[j]<j也保证了之前的next值都是算出来了的。
int KMP(string str, string pat, int *next)
{
int i=0, j=0;
while(i<str.size() && j<pat.size())
{
if(j==-1 || str[i]==pat[j])
i++,j++;
else
j=next[j];
}
if(j==pat.size())
return i-j;
else
return -1;
}
但是看到的各个版本都是
while(i<str.size())
{
…
if(j==pat.size())
{
count++;
j=0;
}
}
这种版本有一个好处，就是可以计算匹配了多少次，所以比较灵活，所以还是选择这种比较好一点。
先介绍这个，再来坑计算next这块骨头，里面其实是利用了之前的一些信息来回溯的，
a[0….k-1]=a[j-k…j-1] k不能再大了，//这里感觉邹博的PPT小标有点问题
那么next[j]=k,
if a[k]==a[j]
next[j+1]=next[j]+1 //这个好理解
else
找next[next[j]],也即a[0…k-1]里面的最长前缀后缀相等，另k=next[j], 如果a[k]==a[j]那么，问题也解决了，next[j+1]=next[k]+1=next[next[j]]+1，也即利用前面的信息，a[0…k-1]中前缀等于后缀，而较短的后缀又等于a[j-k…j-1]的后缀，
因此可以推出。如果不等继续回溯，核心是k=next[k]语句
因此有了下面的CalcNext代码：
void CalcNext(string str, int *next, int n)
{
next[0]=-1;
int k;
for(j=0;j<=n-2;j++)
{
k=next[j];
while(k!=-1 && str[k]!=str[j])
k=next[k];
//if(k!=-1)
next[j+1]=k+1;
//else
// next[j+1]=0;
}
}
我后来看了下邹博代码，发现循环退出好像k= !=-1 可以统一起来，因为next 为负只有-1 一种可能，也只是next[0]，所以似乎代码可以更简洁些。