yxCoding

I am a coder

连接两个头尾重合的字符串(KMP算法应用)

yxjoey posted @ 2008年4月14日 09:22 in C语言 with tags c 程序 , 2932 阅读

连接字符串A, B,但是要求把字符串A的尾部和B的头部重复的地方合并;
例如:
A: "12345"
B: "45678"

那么A+B = "12345678";

我第一个想法就是对A的每个位置都去检测剩下的是否和B可以合并,不过实现的效率很低O(strlen(A)*strlen(B)). 程序如下:

  1. char* catenate(char *str1, char *str2){
  2.   char *p, *q;
  3.   char *r = (char *)malloc(strlen(str1)+strlen(str2)+1);
  4.   int i=0;
  5.   while(*str1!='\0'){
  6.     p = str1;
  7.     q = str2;
  8.     while(*p!='\0'&&*q!='\0'&&*p==*q){
  9.       p++;
  10.       q++;
  11.     }
  12.     if(*p=='\0')
  13.       break;
  14.     r[i++] = *str1++;
  15.   }
  16.   while(*str2!='\0')
  17.     r[i++] = *str2++;
  18.   return r;
  19. }
  20.  

 

 优化:

仔细看这个验证是否可以合并的过程,其实也就是字符串匹配,因此可以利用KMP字符串匹配算法来做,新改进的程序效率可以达到O(strlen(A)+strlen(B))
新改进的程序如下

计算next数组的函数:

  1. void calnext(char *str, int next[]){
  2.   int i;
  3.   next[0] = -1;
  4.   for(i=1; i<strlen(str); i++){
  5.     int value = next[i-1];
  6.     while(value>=0&&str[value+1]!=str[i]){
  7.       value = next[value];
  8.     }
  9.     if(str[value+1]==str[i])
  10.       next[i]=value+1;
  11.     else
  12.       next[i]=-1;
  13.   }
  14. }
  15.  

连接函数:

  1. char *catenate_kmp(char *str1, char *str2){
  2.   int *next = (int *)malloc(strlen(str2));
  3.   calnext(str2, next);
  4.   char *r = (char *)malloc(strlen(str1)+strlen(str2)+1);
  5.   char *p = str1, *q = str2;
  6.   int i=0;
  7.   while(*p!='\0'){
  8.     if(*p==*q){
  9.       r[i++]=*p;
  10.       p++;
  11.       q++;
  12.     }else{
  13.       int k = q-str2;
  14.       if(k==0){
  15.         r[i++]=*p;
  16.         p++;
  17.       }else{
  18.         q = &str2[next[k-1]+1];
  19.       }
  20.     }
  21.   }
  22.   while(*q!='\0'){
  23.     r[i++]=*q++;
  24.   }
  25.   r[i]='\0';
  26.   return r;
  27. }

其实就是稍作修改的kmp算法,不同之处在于,当q到str2的末端,而p没有到末端的时候,也要回溯(原本的kmp算法在这时候应该算找到解,然后结束匹配)。

KMP算法真是一个高效的算法啊。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter