BF算法

hehexixi

1. // 返回子串T在主串S中第pos个字符之后的位置
   
2. // 若不存在，则返回0
   
3. // T非空，1 <= pos <= strlen(S)
   
4. // 注意：我们这里为了表述方便，字符串使用了第一个元素表示长度的方式。
   
5. 
   
6. int index( String S, String T, int pos )
   
7. {
   
8.         int i = pos;        // i用于主串S中当前位置下标
   
9.         int j = 1;                // j用于子串T中当前位置下标
   
10.         
    
11.         while( i <= S[0] && j <= T[0] )        // i或j其中一个到达尾部即终止搜索！
    
12.         {
    
13.                 if( S[i] == T[i] )        // 若相等则继续下一个元素匹配
    
14.                 {
    
15.                         i++;
    
16.                         j++;
    
17.                 }
    
18.                 else                                // 若失配则j回溯到第一个元素从新匹配
    
19.                 {
    
20.                         i = i-j+2;                // i回溯到上次匹配首位的下一个元素，这是效率低下的关键！
    
21.                         j = 1;
    
22.                 }
    
23.         }
    
24.         
    
25.         if( j > T[0] )
    
26.         {
    
27.                 return i - T[0];
    
28.         }
    
29.         else
    
30.         {
    
31.                 return 0;
    
32.         }
    
33. }

复制代码

假设S[7] = 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这一行代码的意思