月度归档:2015年10月

模式匹配算法KMP算法

一种改进后的模式匹配算法是(Knuth Morris Pratt)共同设计的,所以称之为 “KMP模式匹配算法”

KMP算法基本思想:
设s为目标串
设t为模式串
设i 和 j 分别指示目标串和模式串中待比较的字符位置,
开始时, 设 i=0 j =0;
如果s[i] = t[j] 则 i 和 j 的值分别增加1 ,反之i不变 j的值退回之 j=next[j]的位置
然后再对 s[i] t[j]进行比较,依次类推:
(1) j值退回到某个 j =next[j]时,有s[i] t[j] 则指针的值各增加1后,再继续匹配
(2) j值退回到 j = -1 ,此指令指针的值各增加1 即下一次对 s[i+1] 和 t[0]进行比较

KMP算法:

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

 int Next[MAXSTRLEN];

 int KMPIndex(SString s,SString t)
 {
   int i,j,v;
   i = 0;
   j = 0;
  
   while(i < s.len && j < t.len)
   {
     if(j == -1 || s.ch_string[i] == t.ch_string[j]){
         i ++;
         j ++;
      }else
      {
       j = Next[j];
      }
   }
   
  if(j >= t.len)
     v = j-t.len;
  else
    v = -1;


  return v;


 }

从KMP算法中,Next数组关系着整个模式模式串匹配时的回退情况

例:
t = ‘aaab’;
当j =0 Next[j] =-1;
当j =1 Next[j] = 0;
当j =2 有 t[0]=[t1] =’a’ 所以 Next[j] =1 ;
当J=3 t[0]t[1] = t[1]t[2] =’aa’ 即 Next[j] =2;

getNext函数

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

int NEXT[MAXSTRLEN];

void getNext(SString s)
 {
   int i,k;
   k = -1;
   j = 0;
   Next[0] = -1;
   
   while(j < t.len -1)
   {
       if( k == -1 || t.ch_string[j] == t.ch_string[K])
        {
          j ++;
          k ++;
          Next[j]  = k;
        }else
         k = Next[k];
   }
 }

相关阅读:
模式匹配算法 BF

重温C语言排序算法—算法设计

排序:
就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际的优秀算法,需经过大量的推理和分析和实践

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;
 
   }