在串T中查找是否有与串P相等的子串,则称串T为目标(Target),把P称为模式(Pattern)。
称查找模式在目标中的匹配位置的运算为模式匹配(Pattern matching)。
简单模式匹配算法
BF算法 (又称古典的、经典的、朴素的、穷举的)
带回溯,速度慢
【算法思想】
将主串T的第pos个字符和模式P的第1个字符比较,
若相等,继续逐个比较后续字符;
若不等,从主串T的下一字符(pos+1)起,重新与P第一个字符比较。
直到主串T的一个连续子串字符序列与模式P相等。返回值为T中与P匹配的子序列第一个字符的序号,即匹配成功。
否则,匹配失败,返回值 -1。代码如下:
1 int NaiveStrMatching(string T, string P) 2 { 3 int i = 0, j = 0; 4 int plen = P.length(); 5 int tlen = T.length(); 6 if(tlen < plen) return -1; 7 while(i < tlen && j < plen) 8 { 9 if(T[i] == P[j]) 10 { 11 i ++; 12 j ++; 13 } 14 else 15 { 16 i = i - j + 1; //下一趟比较 17 j = 0; 18 } 19 } 20 if(j >= plen) return i - j; //匹配成功 21 else return -1; 22 }