利用“定长顺序储存”实现串的模式匹配（BF算法）

//1. 利用“定长顺序储存”实现串的模式匹配（BF算法）；

#include<stdio.h>

#define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN+1];

int Index(SString S,SString T,int pos){

       int i=pos,j=1;

       while(i<=S[0]&&j<=T[0]){

              if(S[i]==T[j]){

                     ++i;++j;

              }

              else{

                     i=i-j+2;//i指针回溯  i回到原位置是i - j + 1 ,所以i退到远位置的下一个位置是i - j + 1 + 1

                     j=1;//指针后退重新开始匹配 

              }

       }

              if(j>T[0]){ //如果j > len(T)，说明模式串T与S中某子串完全匹配

                     return i-T[0];//因为i是已经自增过一次了，所以是i-len(T)而不是i-len(T)+1

              }

              else return 0; 

}//BF算法

void Creat(SString &S){

       int i=1;

      while((S[i]=getchar())!=‘\n‘){//S[i]作数组 getchar()作输入 S[i]=getchar()不等于‘\n‘ 就i++一个一个的输入数据

              i++;

       }

       S[0]=i-1;//i的前面空出一个 S[0]作长度

}//输入

void Print(SString S){

       int i;

       for(i=1;i<=S[0];i++){//i的取值范围

              printf("%c",S[i]);

       }

       printf("\n");

}//输出

int main(){

       int pos;

       SString S,T;//申请SString的变量S，T

       printf("请输入主串的数据：\n");

       Creat(S);

       printf("请输入子串的数据：\n");

       Creat(T);

       printf("请输入定位到哪个位置匹配：\n");

       scanf("%d",&pos);

       int index=Index(S,T,pos);

       if(index==0){

              printf("找不到此位置！");

       }

       else printf("此位置在%d",index);

       return 0;

}

利用“定长顺序储存”实现串的模式匹配（BF算法）

原文：https://www.cnblogs.com/cherrysnake/p/14876241.html