字符串匹配-BF算法

题目: 有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 请找到模式串在主串中第一次出现的位置; 提示: 不需要考虑字符串大小写问题, 字符均为小写字母;

BF算法-爆发匹配算法
思路：

1. 使用i，j分别指向主串S和模式串T当前比较字符的下标，i初值为pos，j初值为1；
2. 如果2个串均为比较到串尾,即i和j均小于等于S和T的长度时, 则循环执行以下的操作:

• S[i]和T[j]比较,若相等,则i 和 j分别指示串中下一个位置,继续比较后续的字符;
• 若不相等,指针后退重新开始匹配. 从主串的下一个字符串(i = i - j + 2)起再重新和模式第一个字符(j = 1)比较;
  3.如果j > T.length,说明模式T中的每个字符串依次和主串S找中的一个连续字符序列相等,则匹配成,返回和模式T中第一个字符的字符在主串S中的序号(i-T.length);否则匹配失败,返回0;

int Index_BF(String S, String T,int pos){
    //i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配
    int i = pos;
    //j用于子串T中当前位置下标值
    int j = 1;
    
    //若i小于S的长度并且j小于T的长度时，循环继续
    while (i <= S[0] && j <= T[0]) {
        
        //比较的2个字母相等,则继续比较
        if (S[i] == T[j]) {
            i++;
            j++;
        }else
        {
            //不相等,则指针后退重新匹配
            
            //i 退回到上次匹配的首位的下一位;
            //加1,因为是子串的首位是1开始计算;
            //再加1的元素,从上次匹配的首位的下一位;
            i = i-j+2;
            
            //j 退回到子串T的首位
            j = 1;
        }}
    
    //如果j>T[0],则找到了匹配模式
    if (j > T[0]) {
        //i母串遍历的位置 - 模式字符串长度 = index 位置
        return  i - T[0];
    }else{
        return -1;
    }
    
}