连接两个头尾重合的字符串（KMP算法应用）
连接字符串A, B，但是要求把字符串A的尾部和B的头部重复的地方合并；
例如:
A: "12345"
B: "45678"
那么A＋B = "12345678";
我第一个想法就是对A的每个位置都去检测剩下的是否和B可以合并，不过实现的效率很低O(strlen(A)*strlen(B)). 程序如下:
-
char* catenate(char *str1, char *str2){
-
char *p, *q;
-
char *r = (char *)malloc(strlen(str1)+strlen(str2)+1);
-
int i=0;
-
while(*str1!='\0'){
-
p = str1;
-
q = str2;
-
while(*p!='\0'&&*q!='\0'&&*p==*q){
-
p++;
-
q++;
-
}
-
if(*p=='\0')
-
break;
-
r[i++] = *str1++;
-
}
-
while(*str2!='\0')
-
r[i++] = *str2++;
-
return r;
-
}
-
优化：
仔细看这个验证是否可以合并的过程，其实也就是字符串匹配，因此可以利用KMP字符串匹配算法来做，新改进的程序效率可以达到O(strlen(A)+strlen(B))
新改进的程序如下
计算next数组的函数:
-
void calnext(char *str, int next[]){
-
int i;
-
next[0] = -1;
-
for(i=1; i<strlen(str); i++){
-
int value = next[i-1];
-
while(value>=0&&str[value+1]!=str[i]){
-
value = next[value];
-
}
-
if(str[value+1]==str[i])
-
next[i]=value+1;
-
else
-
next[i]=-1;
-
}
-
}
-
连接函数：
-
char *catenate_kmp(char *str1, char *str2){
-
int *next = (int *)malloc(strlen(str2));
-
calnext(str2, next);
-
char *r = (char *)malloc(strlen(str1)+strlen(str2)+1);
-
char *p = str1, *q = str2;
-
int i=0;
-
while(*p!='\0'){
-
if(*p==*q){
-
r[i++]=*p;
-
p++;
-
q++;
-
}else{
-
int k = q-str2;
-
if(k==0){
-
r[i++]=*p;
-
p++;
-
}else{
-
q = &str2[next[k-1]+1];
-
}
-
}
-
}
-
while(*q!='\0'){
-
r[i++]=*q++;
-
}
-
r[i]='\0';
-
return r;
-
}
其实就是稍作修改的kmp算法，不同之处在于，当q到str2的末端，而p没有到末端的时候，也要回溯(原本的kmp算法在这时候应该算找到解，然后结束匹配)。
KMP算法真是一个高效的算法啊。。
评论 (0)
yxjoey
最新评论
最新留言
友情链接
我的豆瓣收藏
浏览计数器
64196