第二关，KPM算法和next函数值

第二关，KPM算法和next函数值

#include<cstring>
#include<iostream>
using namespace std;#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255   		//用户可在255以内定义最长串长
typedef char SString[MAXSTRLEN+1];		//0号单元存放串的长度Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串Tint i;if (strlen(chars) > MAXSTRLEN)return ERROR;else {T[0] = strlen(chars);for (i = 1; i <= T[0]; i++)T[i] = *(chars + i - 1);return OK;}
}
//算法4.3　计算next函数值
void get_next(SString T, int next[])
{ //求模式串T的next函数值并存入数组next/**********************Begin**********************/int i = 1, j = 0;next[1] = 0;while (i < T[0])if (j == 0 || T[i] == T[j]) //根据模式串T，求出next数组{++i;++j;next[i] = j;}elsej = next[j];/**********************End*************************/
}//get_next//算法4.2　KMP算法
int Index_KMP(SString S, SString T, int pos, int next[])
{ 	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法//其中，T非空，1≤pos≤StrLength(S)/**********************Begin**********************/int i = pos, j = 1;while (i <= S[0] && j <= T[0])if (j == 0 || S[i] == T[j]) // 继续比较后继字{++i;++j;}else //利⽤next数组进⾏匹配（主串指针不回溯）j = next[j]; // 模式串向右移动if (j > T[0]) // 匹配成功return i - T[0];elsereturn 0;/**********************End*************************/
}//Index_KMPint main()
{SString S;char s[MAXSTRLEN];cin>>s;StrAssign(S,s) ;SString T;char t[MAXSTRLEN];cin>>t;StrAssign(T,t) ;int *p = new int[T[0]+1]; // 生成T的next数组get_next(T,p);int n=Index_KMP(S,T,1,p);if(n)cout<<"主串和子串在第"<<n<<"个字符处首次匹配\n";elsecout<<"主串和子串没有匹配上\n";return 0;
}