KMP算法——字符串匹配

　　正直找工作面试巅峰时期，有幸在学校可以听到July的讲座，在时长将近三个小时的演讲中，发现对于找工作来说，算法数据结构可以算是程序员道路的一个考量吧，毕竟中国学计算机的人太多了，只能使用这些方法来淘汰了，但是说到一点，互联网公司找的是会写代码，有思想的程序员，而不是一些公务员，你招的不是那些搞行测的，你是要做技术的，发现今年某些公司，出一些乱七八糟的行测题。有点偏题了！！！

　　July讲座中我印象最深刻的是KMP算法，以前对KMP算法懵懵懂懂的，今天听完以后，有了一些全新的认识，不能说懂吧，最起码代码可以自己写出来了。

#include <iostream>
#include <string.h>
using namespace std;
void getNext(const char *p, int next[])
{
    int j=-1;
    next[0]=-1;
    int n=strlen(p);
    for(int i=0;i<n-1;)
    {
        if(j==-1 || p[i]==p[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
int kmpSearch(const char *s,const char *p)
{
    int slen=strlen(s);
    int plen=strlen(p);
    int i=0,j=0;
    int next[plen+1];
    getNext(p,next);
    while(i<slen && j<plen)
    {
        if(j==-1 || s[i]==p[j])
        {
            i++;
            j++;
        }
        else
            j=next[j];
    }
    if(j==plen)
        return i-j;
    else
        return -1;
}
int main()
{
    const char *s="BBCABCDABABCDABDABDE";
    const char *p="ABCDABD";
    int index = kmpSearch(s,p);
    cout << "index = " << index << endl;
    return 0;
}