KMP模式匹配算法

字符串模式匹配算法KMP算法及其改进

 //得到子串搜索时的回退个数
 void get_next(String T, int *next)
 {
 	int i = 0, j = -1;//i,j分别表示子串中前缀和后缀的下标
 	next[0] = -1;//next初始化为-1
 	while(i < T.length)
 	{
 		if(j == -1 || T[i] == T[j])
 		{
 			i++;
 			j++;
 			if(T[i] != T[j])
 				next[i] = j;
 			else
 				next[i] = next[j];
 		}
 		else
 			j = next[j];
 	}
 }

匹配算法

//S为主串，T为子串，从主串中第pos位开始匹配

 int Index_KMP(String S, String T, int pos)

 {
 	int next[255];//存放子串回退个数
 	int i = 0, j = 0;//i,j分别为主串S和子串T的下标。
 	//获得next
 	get_next(T,next);

 	while(i<S.length && j<T.length)
 	{
 		if(j == -1 || S[i] == T[j])
 		{
 			i++;  j++;
 		}else
 			j = next[j];
 	}
 	//出while只有三种情况：a.主串遍历完，子串未完则---》查找失败，为找到
 	//b.主串完子串完，则找到返回 i-T.length+1
 	//c.主串未完，子串完  找到  返回结果  i-T.length+1
 	if(j >= T.length)
 	{
 		return i-T.length+1;
 	}else
 		return 0;//未找到
 }