kmp代码编译分析

menglv · 发表于 2015-6-3 20:01:24

//下面是kmp算法
//*********************************************************//
void get_next(char* s,int* next) //s表示模式串，next表示next数组的头指针
{
int length=strlen(s);
int i=1,j=0;
//i表示模式串的每一个元素的指针，每次加1递增，j表示前缀串中，每一个元素的位置。
next[0]=-1;
for(;i<length;i++){ //开始递归模式串中每一个元素
if(s[i]==s[j]){ //如果当前元素和前缀的第一个元素相等，表示开始匹配前缀和后缀串，j++表示前缀的下一个位置的元素。
next[i]=j; //同时把当前next[i]设置成为前缀中的位置。
j++;
}else{ //当前位置和前缀串中的不一致，
if(s[i]==s[0]){ //如果当前位置和前缀串中的第一个元素相同，那么表示又重新开始匹配新一轮后缀
next[i]=0; //重新开始匹配后缀，所以next的值是0，表示前缀的第一个元素的位置
j=1; //前缀的指针变成下一个位置
}
else{ //如果当前位置和第一个位置的元素也不相同，表示没有这样的以这个元素为前缀的字符串，把这个next值变成-1.
next[i]=-1;
j=0;
}
}
}
}
//target是目标串，s是模式串，data是next数组
void find(char *target,char *s,int* data){
int i=0; //i是目标串的指针
int j=0; //j是模式串的指针
for(;i<strlen(s);){
if(s[i]==target[j]){ //如果模式串和目标串匹配
if(j==strlen(target)-1){//如果完全匹配，就说明在目标串中找到了模式串
printf("start:%d\n",i-j+1);
break;
}else{
j++;//否则继续比较下一个字符
i++;
}
}else{ //如果这两个字符不匹配
if(j==0||data[j-1]==-1){ //如果是和模式串的第一个字符做匹配失败，或者next数组的前一个值是-1，表示前一个位置的后缀，在当前模式串中找不到前缀，所以这时，i指针需要向前移动，
j=0;
i++;
}else{ //表示匹配前缀的后一个位置的元素。
j=data[j-1]+1;
}
}
}
}

复制代码

menglv · 发表于 2015-6-4 08:59:05

看来那些垃圾代码确实是strlen，那个代码之前是字符串查找的，而strlen遇到0x00会停止。
我将其改成hex查找，所以出错。

现在修正一下就可以用了：

飘云 · 发表于 2015-6-4 09:46:12

{:soso_e100:}/...你把char 换成 unsigned char
len 传进来不就好了？

menglv · 发表于 2015-6-4 09:48:32

本帖最后由 menglv 于 2015-6-4 09:53 编辑

      //下面是kmp算法，可以查找hex
//*********************************************************//
      void get_next(char* s,int* next,int length) //s表示模式串，next表示next数组的头指针
{
//int length=strlen(s);
int i=1,j=0;
                           //i表示模式串的每一个元素的指针，每次加1递增，j表示前缀串中，每一个元素的位置。
next[0]=-1;
for(;i<length;i++){       //开始递归模式串中每一个元素
      if(s==s[j]){       //如果当前元素和前缀的第一个元素相等，表示开始匹配前缀和后缀串，j++表示前缀的下一个位置的元素。
         next=j;       //同时把当前next设置成为前缀中的位置。
         j++;
      }else{                //当前位置和前缀串中的不一致，
         if(s==s[0]){ //如果当前位置和前缀串中的第一个元素相同，那么表示又重新开始匹配新一轮后缀
            next=0;    //重新开始匹配后缀，所以next的值是0，表示前缀的第一个元素的位置
            j=1;          //前缀的指针变成下一个位置
         }
         else{             //如果当前位置和第一个位置的元素也不相同，表示没有这样的以这个元素为前缀的字符串，把这个next值变成-1.
            next=-1;
            j=0;
         }
      }
}
}

//target是目标串，s是模式串，data是next数组
void find(char *target,char *s,int* data,int l,int l2){
  //l 为文件长度，l2 为特征码长度
  int i=0;             //i是目标串的指针
  int j=0;             //j是模式串的指针
  for(;i<l;){
   if(s==target[j]){ //如果模式串和目标串匹配
      if(j==l2-1){//如果完全匹配，就说明在目标串中找到了模式串
         printf("start:%d\n",i-j+1);
         break;
      }else{
         j++;//否则继续比较下一个字符
         i++;
      }
   }else{ //如果这两个字符不匹配
   if(j==0||data[j-1]==-1){ //如果是和模式串的第一个字符做匹配失败，或者next数组的前一个值是-1，表示前一个位置的后缀，在当前模式串中找不到前缀，所以这时，i指针需要向前移动，
            j=0;
            i++;
         }else{             //表示匹配前缀的后一个位置的元素。
            j=data[j-1]+1;
         }
   }
  }
}

menglv · 发表于 2015-6-4 09:52:41

飘云发表于 2015-6-4 09:46
/...你把char 换成 unsigned char
len 传进来不就好了？

主要是strlen遇到0x00就会截止，所以我将len传进来就可以了，char倒是无所谓。

飘云 · 发表于 2015-6-4 10:27:09

menglv 发表于 2015-6-4 09:52
主要是strlen遇到0x00就会截止，所以我将len传进来就可以了，char倒是无所谓。

.。不用strlen啊，，len外部算好~~ 随便改改源代码就OK了

		自动登录	找回密码
密码			加入我们

[C/C++] kmp代码编译分析

点评

点评