c语言字符串模式匹配算法

字符串的模式匹配算法是一种重要的串运算。
例:设定 s t两个串,在串s中找到等于t的子串的过程我们称之为“模式匹配”。 其中串s称之为 “主串”,如果在串中找到同t相同的字串,
那么我们就称之为”匹配成功“,否则“匹配失败”。



模式匹配算法

一种直观的模式匹配算法是布鲁特-福斯算法-BF算法。
BF算法的核心思想:
将s中的第一个字符与t中的第一个字符进行比较,若不同,就将s中的第二个字符与s进行比较,依次比较,知道s中的某一个字符与t中的第一个字符相等,再将它们之后的字符进行比较,若也相同,则继续比较,依次类推,
最后将出现两种情况:
1 在s中找到和t相同的子串,表明匹配成功
2 将s中所有的字符都检测完毕,但是还未找到与t相同的子串,表明匹配失败。

  #define MAXSTRLEN 256
  typedef struct{
   char ch_string[MAXSTRLEN];
   int len;
  } SString

   int BFIndex(SString s,SString t){
     int i,j,v;
     i = 0; //主串开始搜索位置
     j = 0; //子串已匹配位置
  
    while(i < s.len && j < t.len)
       {
         if(s.ch_string[i] == t.ch_string[j])
          {
            //字符匹配成功
             i++;
             j++;
          }else
          {
              //字串匹配失败 还原至上次匹配成功的位置
              i=i-j+1;
              j =0;
          }
       }


     if(j > t.len)
          v = i-t.len; //返回匹配成功的起始位置
         
          v =-1;      //返回-1 匹配失败
          return v;
 
   }