BF算法
// 返回子串T在主串S中第pos个字符之后的位置// 若不存在，则返回0
// T非空，1 <= pos <= strlen(S)
// 注意：我们这里为了表述方便，字符串使用了第一个元素表示长度的方式。
int index( String S, String T, int pos )
{
int i = pos; // i用于主串S中当前位置下标
int j = 1; // j用于子串T中当前位置下标
while( i <= S && j <= T ) // i或j其中一个到达尾部即终止搜索！
{
if( S == T ) // 若相等则继续下一个元素匹配
{
i++;
j++;
}
else // 若失配则j回溯到第一个元素从新匹配
{
i = i-j+2; // i回溯到上次匹配首位的下一个元素，这是效率低下的关键！
j = 1;
}
}
if( j > T )
{
return i - T;
}
else
{
return 0;
}
}
假设S = Q,那么在i = 7, j = 2时候不匹配，所以 i = i - j + 2,所以 i = 7 - 2+2 =7
若在i = 8 ,j = 3时候不匹配那么i = 8 - 3 + 2=7怎么还是等于7
求解答i = i - j +2这一行代码的意思
页:
[1]