/*

*功能：使用kmp算法对字符串进行匹配，

* 1、一般情况下我们主串和模式串匹配到了一定程度，比如匹配到了5个（主模长度都比5大），但是第6个字符不相等

那么我们接下来需要匹配的是在主串的什么地方开始，也可能是匹配的5个中后面有几个正好是模式串的开头，那么我们如何开始下一个子串的匹配

2、当主串的第i个字符与模式串的第j个字符匹配不等的时候，假设此时应该和模式中第k（k<j)个字符继续比较

3、我们已经得到匹配的字符串是k======================================从模式第k个开始比较，k-1就是开始新的匹配的时候前面不用比较的个数

4、j=================================模式串第j个字符失配（前面那次比较得到的结果，下一次就是用到k的那次）

5、i=================================主串第i个字符失配

6、我们先假设p:1到p:k-1是模式串，然后s:1到s:m是主串

7、模式串中后半部分和主串前面重合，不需要接下来匹配的部分是 { p:j-k+1 。。。 p:j-1 } 这个就是我们模式串中和主串后部分重合的地方

j-k+1这个就是我们模式串中前面不用再和主串比较的起始位置，其实就是把失配的地方前移后面不用比较的个数j-(k-1)

8、主串中我们也吧他前移k-1个字符，也就是我们不用比较的那些字符起始位置 { s:i-(k-1)。。。s:i-1 }

9、由上可得模式串中已经不需要和主串比较的部分也就是 { p:1。。。p:k-1 } 和 { s:i-(k-1)。。。s:i-1 } 相等

10、而{ s:i-(k-1)。。。s:i-1 } 就是我们后面不用比较的部分又和 { p:j-k+1 。。。 p:j-1 }相等

11、那么 { p:j-k+1 。。。 p:j-1 } 和 { p:1。。。p:k-1 } 相等

12、所以模式串满足11步的子串的时候，我们只需要把主串在不相等的地方开始，而子串只需要从第k个字符开始和主串的第i个字符开始比较

13、那么我们可以根据j的值来算k的值，也就是下一个k的值是next[j],我们让next[j] = k - 1;

14、计算k的公式就是 { p:j-k+1 。。。 p:j-1 } == { p:1。。。p:k-1 } 并且 1 < next[j] < j 取最大值（也就是可以不用比较的最大值），并且{ p:j-k+1 。。。 p:j-1 } == { p:1。。。p:k-1 }两个的序号不能一样

15、-----------------------------------如何获取对应{ p:j-k+1 。。。 p:j-1 } == { p:1。。。p:k-1 }的k值-------------------------------------------------------------------------------------------------------------------------

16、我们使next[j] = k,用模式串的匹配条件和1 < next[j] < j 来取得k值的

17、我们假设next[j] = k可以递推出下一个next[j+1]的值，通过p:k与p:j的值是否相等

18、这个就是把模式串当做主串和模式串进行比较，寻找相同的部分

19、我们模式串的next数据和我们要匹配的主串无关，只和我们的模式串自己相关

*时间：2015年7月18日19:12:23，2015年7月26日16:37:17

*文件：kmp.h

*作者：cutter_point

*/

#ifndef KMP_H

#define KMP_H

#include "SString.h"

class KmpString : public SString

{

int *next;

public:

KmpString(unsigned char *css, unsigned int len) :SString(css, len) {}

int index_KMP(SString T, unsigned int pos);

void get_next(SString T);

int* getNext() { return next; }

};

#endif