题目: 有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 请找到模式串在主串中第一次出现的位置; 提示: 不需要考虑字符串大小写问题, 字符均为小写字母;
BF算法-爆发匹配算法
思路：
- 使用i，j分别指向主串S和模式串T当前比较字符的下标，i初值为pos，j初值为1；
- 如果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;
}
}
