简单匹配算法

1、3113008094 詹宏宇信安1简单匹配算法：?算法设计思想：等，从主串S的下一字符(pos+1 )起，重新与T第 一个字符比较。?将主串S的第pos个字符和模式T的第1个字符比较，嗒相等，继续逐个比较后续字符；嗒不?直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。?否则，匹配失败，返回值 0.int Fin d(char*target, char* pat) inti=0,j=0; |intlengthP =strlen(pat), lengthT =strlen(target);while(i=le ngthT-le ngthP)j

2、=0;while(targeti=patj&jle ngthP)i+；j+；if(j=le ngthP)return i-j; /串pat扫描完，匹配成功elsei=i-j+1;不匹配，做下一趟比较return -;Kmp算法实现:第一步，先把模式 T所有可能的失配点j所对应的nextj计算出来; 第二步：执行定位函数 Index_kmp (与BF算法模块非常相似)1. int KMPindex(SString S, SString T,int pos)2. 3. if (pos S0 ) exit(ERROR);4. int i = pos, j =1;5. while (i= S0 & j

3、 T0) return i - T0;14. return ERROR;15. 完整实现代码：/ Test.cpp : Defines the entry point for the console application./#include stdafx.h#include #include stdlib.h#include using n amespacestd;/宏定义#define TRUE 1#define FALSE 0 #define OK 1#define ERROR 0#define MAXSTRLEN 100typedef char SStringMAXSTRLEN + 1

4、;void GetNext(SString T, int next);int KMPindex(SString S, SString T,int pos);/*/*返回子串T在主串S中第pos位置之后的位置，若不存在，返回0*/*/int KMPindex(SString S, SString T,int pos)if (pos S0 ) exit(ERROR);int i = pos, j =1;int nextMAXSTRLEN;GetNext( T, next);while (i= S0 & j T0) return i - T0;return ERROR;/*/* 求子串nexti 值的算法*/void GetNext(SString T, int next) int j = 1, k = 0;next1 = 0;while (j T0)if (k = 0 | Tj=Tk) +j; +k; nextj = k; else k = nextk;void main()SString S = 13,a , b,a ,b , c ,a , b , c , a , c ,b , a ,b ;SStrin