BF（回溯）算法解析
2020-12-21 本文已影响0人
dreamer11
1 BF（回溯）算法
若看目标串T是否是源串S的子串，可采用BF算法，具体实现如下所示：
设T = “qwer”, S = “aqwdqwerd”
S = a q w d q w e r d
T = q w e r
第一步将T[0](q)与S[0](a)比较，q不等于a；
第二步将T[0](q)与S[1](q)比较，相等；
第三步将T[1](w)与S[2](w)比较，相等；
第四步将T[2](e)与S[3](d)比较，不相等；
此时将T从头再来，与S[2]比较；
再依次进行上面的重复步骤，来判断T是否是S的子串。
具体c++代码见下：
