kmp

kmp算法

最开始要写一个删除子串的算法， 原以为这是一个简单的问题，看来还是眼高手低，我可能要多学习基础的东西。一开始我想要用指针的循环来解决这个问题，可是忙活了半天，最后还是失败告终。我就打算干脆用数组吧，顺便复习一下kmp算法，实践操作一下。提到kmp算法，疯狂失败之后我开始一步一步debug，然后发现一个地方-1>3返回了true，问题的根本就是strlen()函数返回值是size_t类型，也就是无符号整型，由于优先级的问题又把-1转换成了无符号型，于是导致了上边说的问题，经过改正终于实现了kmp算法。下面是我的代码：

#include<iostream>
#include<cstring>
using namespace std;

void get_next(char s[],int next[]){
	int i=0,j=-1;
	next[0]=-1;
	while(i<strlen(s)-1){
		if(j==-1||s[i]==s[j]){
			++i;
			++j;
			if(s[i]!=s[j]) next[i]=j;
			else next[i]=next[j];
		}
		else j=next[j];
	}
}

int main(){
	char s[256];
	char t[256];
	int next[256];
	cin>>s;
	cin>>t;
	get_next(s,next);
	int i=0,j=0;
	while((i<(int)strlen(s))&&(j<(int)strlen(t))){
		if(j==-1||s[i]==t[j]){
			++i;
			++j;
		}
		else j=next[j];
	} 
	if(j>=strlen(t)) cout<<i-strlen(t)+1<<endl;
	return 0;
}