写在前面：

   代码中有的是i，j，有的是j，k，总之不唯一啊@！！！这个一定要弄清楚！！！我没有统一。。

 

从0开始的字符串，加速版。 

void getnext() {
	next[0]=-1;
	int k=-1,j=0;
	while(j<len2-1) {
		if(k==-1||str2[k]==str2[j]) {
			k++;
			j++;
			if(str2[k]!=str2[j]) next[j]=k;
			else next[j]=next[k];
		} else k=next[k];
	}
}

从1开始，不加速。 

void get_next() {
	int i,k;
	i=1;
	k=0;
	next[1]=0;
	while(i<len2) {
		if(k==0||b[i]==b[k]) {
			i++;
			k++;
			next[i]=k;
		} else k=next[k];
	}
}

从0开始，不加速 

void getnext() {
	next[0]=-1;
	int k=-1,j=0;
	while(j<len2-1) {
		if(k==-1||str2[k]==str2[j]) {
			k++;
			j++;
			next[j]=k;
		} 
		else k=next[k];
	}
}

从0开始，这应该也是个不加速，但是有while加速的https://www.cnblogs.com/Rubbishes/p/7564992.html

inline void GetNext()
{
    int i = 0, j = -1;
    Next[i] = j;
    while(i < moL){
        while( j!=-1 && mo[i]!=mo[j]) j = Next[j];
        Next[++i] = ++j;
    }
}

 

int KMP()  返回起始位置的，要求串s和模板串p都是从0开始的。

int KmpSearch(char* s, char* p) {
	int i = 0;
	int j = 0;
	int sLen = strlen(s);
	int pLen = strlen(p);
	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 KMP() {
//	int next[10005];
	int len1=strlen(str1);
	int len2=strlen(str2);
	getnext();
	int i=0,j=0;
	int cnt=0;
	while(i<len1) {
		if(j==-1||str1[i]==str2[j]) {
			i++;
			j++;
		} else {
			j=next[j];
		}
		if(j==len2) {
			cnt++;
			j=next[j];
		}
	}
	return cnt;
}

返回不重叠的字符串的个数（剪花布条）

    字符串从1开始读入的。

int KMP() {
	int i=1,j=1,cnt=0;
	while(i<=len1) {

		if(j==0||a[i]==b[j]) {
			i++;
			j++;
		} 
		else j=next[j];
		if(j>d2) {
			cnt++;
			j=1;
		}//不能是等于 是大于 因为上面是//j++ 等于的时候实际上少了一个
	}
	return cnt;
}

 

 

还是不要写从1开始的那个了，因为很多值就不这么巧了。比如next中存的值，不是前缀最大相同个数了，而是相同个数+1了。。比如abcabd，那next[d] = 3了就成，但是应该是共同前缀是2。