串的模式匹配算法_BF算法

#include
#define MANLEN 25
typedef struct
{
    char ch[25];
    int length;
}SString;
int Index_BF(SString S, SString T, int pos)   
//T为模式串, S为主串,   返回模式T在主串S中第pos
//个字符开始第一次出现的位置。若不存在则返回0;
{
    int i = pos, j = 1;
    while(i <= S.length && j <= T.length){  //保证两个串都为超过自身长度
        if(S.ch[i] == T.ch[j]){
            i++;
            j++;
        }
        else{
            i = i - j + 2;  
            // 在主串中后退,退到第n次比较的位置的后一位,
            //进行第n+1次从头(当 j == 0 的位置,也就是
            //模式串的第一个字母)比较。
            j = 1;  //从模式串的第一个开始再重新比较;
        }
    }
    if(j > T.length) return (i - j + 1);
    else return 0;
}
int main()
{
    SString S, T;
    printf("主串长度   = ");
    scanf("%d",&S.length);
    printf("主串内容   = ");
    scanf("%s", S.ch+1);//地址加一 是因为 S.sh[0]不利用
    printf("模式串长度 = ");
    scanf("%d", &T.length);
    printf("模式串内容 = ");
    scanf("%s", T.ch+1);//地址加一 是因为 S.sh[0]不利用
    int i, pos = 1;
    i = Index_BF(S, T, pos);
    if(i == 0)
        printf("match fault");
    else
        printf("match success loc = %d", i);
    return 0;
}

 

 

运行结果:

 

串的模式匹配算法_BF算法_第1张图片
 

你可能感兴趣的