简单匹配算法
- 格式:doc
- 大小:37.00 KB
- 文档页数:4
3113008094 詹宏宇信安1
简单匹配算法:
•算法设计思想:等,从主串S的下一字符(pos+1)起,重新与T第一个字符比较。
•将主串S的第pos个字符和模式T的第1个字符比较,
–若相等,继续逐个比较后续字符;
–若不•直到主串S的一个连续子串字符序列与模式T相等。返回值为S 中与T匹配的子序列第一个字符的序号,即匹配成功。
•否则,匹配失败,返回值0 .
int Find(char*target, char* pat) {
inti=0,j=0;
int lengthP=strlen(pat), lengthT=strlen(target);
while(i<=lengthT-lengthP)
{ j=0;
while(target[i]==pat[j]&&j i++;j++; } if(j==lengthP) return i-j; //串pat扫描完,匹配成功 else i=i-j+1;//不匹配,做下一趟比较 } return –1; } Kmp算法实现: 第一步,先把模式T所有可能的失配点j所对应的next[j]计算出来; 第二步:执行定位函数Index_kmp(与BF算法模块非常相似) 1. int KMPindex(SString S, SString T, int pos) 2. { 3. if (pos <1 || pos > S[0] ) exit(ERROR); 4. int i = pos, j =1; 5. while (i<= S[0] && j <= T[0]) 6. { 7. if (S[i] == T[j]) { 8. ++i; ++j; 9. } else { 10. j = next[j+1]; 11. } 12. } 13. if(j > T[0]) return i - T[0]; 14. return ERROR; 15. } 完整实现代码: // Test.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include "stdlib.h" #include using namespace std; //宏定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSTRLEN 100 typedef char SString[MAXSTRLEN + 1]; 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 <1 || pos > S[0] ) exit(ERROR); int i = pos, j =1; int next[MAXSTRLEN]; GetNext( T, next); while (i<= S[0] && j <= T[0]) { if (S[i] == T[j]) { ++i; ++j; } else { j = next[j]; } } if(j > T[0]) return i - T[0]; return ERROR; } /************************************************************************/ /* 求子串next[i]值的算法 */ 4/************************************************************************/ void GetNext(SString T, int next[]) { int j = 1, k = 0; next[1] = 0; while(j < T[0]){ if(k == 0 || T[j]==T[k]) { ++j; ++k; next[j] = k; } else { k = next[k]; } } } void main(){ SString S = {13,'a','b','a','b','c','a','b','c','a','c','b','a','b'}; SString T = {5,'a','b','c','a','c'}; int pos; pos = KMPindex( S, T, 1); cout<<"Pos:"< }