运行结果和预想的不一样~
题目:编写程序,在两个已知的字符串中查找所有非空的最长公共子串的长度与个数!#include <stdio.h>
#include <string.h>
#define maxline 120
void main(void)
{char *str1,*str2,*tstr;
int len1,len2,k,p,i,slen,count;
str1=(char *) malloc(maxline);
str2=(char *) malloc(maxline);
if(!str1||!str2)
{printf("memory allocation error!\n");
exit(0);
}
printf("input first string:");
gets(str1);
printf("input second string:");
gets(str2);
len1=strlen(str1);
len2=strlen(str2);
if(len1>len2)
{tstr=str1;str1=str2;str2=tstr;slen=len1;len1=len2;len2=slen;}
for(slen=len1;slen>0;--slen)
{for(k=0;k+slen<=len1;++k)
{for(p=0;p+slen<len2;++p)
{for(i=0;i<slen;++i)
if(str1[k+i]!=str2[p+i]) break;
if(i==slen)
count++;
}
}
if(count) break;
}
printf("numbers of substring:%d,length of substring:%d",count,slen);
getche();
}
----------------解决方案--------------------------------------------------------
我不是很明白你的"最长公共子串的长度与个数!"是什么意思
但是我觉得你应该给count出始了
----------------解决方案--------------------------------------------------------
谢谢~,初始化以后没有警告了
但我也还是不明白,字符串的子串到底是指什么?答案是这样解析的:
设置两个字符str1和str2,分别指向两个串,并用len1和len2表示串的长度。假设len1<=len2,那么他们的公共子串的长度不会超过len1.先考察有没有长度为len1的公共子串,若没有,则考察是否有长度为len-1的公共子串。程序为:
#include <stdio.h>
#include <string.h>
#define maxline 120
void main(void)
{char *str1,*str2,*tstr;
int len1,len2,k,p,i,slen,count=0;
str1=(char *) malloc(maxline); /*申请字符串的存储空间 */
str2=(char *) malloc(maxline);
if(!str1||!str2)
{printf("memory allocation error!\n");
exit(0);
}
printf("input first string:");
gets(str1); /*从键盘获取字符*/
printf("input second string:");
gets(str2);
len1=strlen(str1); /*计算串长*/
len2=strlen(str2);
if(len1>len2) /*令str1总是指向长度较短的字符串*/
{tstr=str1;str1=str2;str2=tstr;slen=len1;len1=len2;len2=slen;}
for(slen=len1;slen>0;--slen)
{ /*查找长度为slen的公共字串*/
for(k=0;k+slen<=len1;++k)
{ /*从str1[k]开始查找长度为slen的子串,与str2中的子串进行比较*/
for(p=0;p+slen<len2;++p)
{ /*str2中的子串从str[p]开始*/
for(i=0;i<slen;++i) /*一一比较两个子串中的字符*/
if(str1[k+i]!=str2[p+i]) break;
if(i==slen) /*找到一个最长的公共子串*/
++count;
}
}
if(count) break; /*已经找到至少一个最长的公共子串*/
}
printf("numbers of substring:%d,length of substring:%d",count,slen);
getche();
}
----------------解决方案--------------------------------------------------------
动态规划问题!
呵呵!
----------------解决方案--------------------------------------------------------