串的模式匹配算法

2019-04-14 09:07发布

站内文章 / 模拟电子
10436 0 1213
关于这个算法核心在与理解next[]值的获得 #include #include #include #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define INFEASIBLE -1 typedef int Status; #define MAXSTRLEN 255 typedef int Status; typedef char SString[MAXSTRLEN + 1]; //加一是为了使0号位存放串的长度 int i,j; int next[MAXSTRLEN]; //获得next[i]值的函数 void Getnext(SString T, int next[]) { i = 1; next[1] = 0; j = 0; while (i T[0]) return i - T[0]; else return 0; } //给新字符串赋值，生成一个值等于chars的串T Status StrAssign(SString& T, const char* chars) { if (strlen(chars) > MAXSTRLEN) { //当chars的长度大于最大值时便再最大值处截断 for (int i = 1; i <= MAXSTRLEN; i++) T[i] = *(chars + i - 1); T[0] = MAXSTRLEN; } else { T[0] = strlen(chars); //此时chars长度小于max，则在T[0]存入chars的长度值 for (int j = 1; j <= MAXSTRLEN; j++) T[j] = *(chars + j - 1); return OK; } } int main() { SString P1, P2, S1, S2, T; int pos = 1; char str[MAXSTRLEN]; printf("Please enter the main string "); gets_s(str); StrAssign(P1, str); printf("Please enter the substring "); gets_s(str); StrAssign(P2, str); Getnext(P2,next); printf("The position is :%d", IndexKMP(P1, P2, pos)); }

热门文章