用C语言求连续公共子串的长度
算法:求两个字符串最长的公共子串。
原则:
(1)通过连接的字符串的行和列形成矩阵。
(2)。如果对应于矩阵节点的字符相同，则节点值为1。
(3)当前字符相同的节点的值=左上角(dC语言编程寻找两个字符串的最长公共子串，如“我是学生。”和“你是学生吗？”最长的公共子串是“学生” //一个问题是空格也要算作字符，所以不考虑空格。就像你的例子，最长的公共字符串应该是///" student "，包括空格。还有，我的方法应该不是很好，效率比较低。我只是先保持string //1不动，从第一个字符开始string 2和string 1比较，然后从第二个字符开始string 2和string 1比较，就都结束了。///String 1向右移动一个位置。
# includestdio.h
int main()
{
char str1[100]={0}，str 2[100]= { 0 }；
printf("请输入两个字符串:\ n ")；
gets(str 1)；//读取字符串
gets(str 2)；
char * p1 = str1//用于分别存储str1和str2的当前比较位置。
char * p2 = str2
int max=0，num = 0；//max存储比较后最长的字符串长度，num为本轮比较的常用字符串长度。
char * start//存储最大字符串的起始位置
while(*p1！='\0')//第一个字符串1大循环。
{
p2 = str2//p2是字符串2的第一个地址。
while(*p2！='\0')
{
char * begin = p1//begin是字符串1的当前比较位置。
char * begin2 = p2//begin2是字符串2开始比较的位置。
num = 0；//比较前初始化为0
while(*begin！='\0' *begin2！='\0')//新一轮的比较
{
If(*begin==*begin2) //如果相同，num
{ num开始；begin2}
else break
}
If(nummax) //如果新比较的字符串更长，将替换最大值和起始内容。
{ max = num
start = p1}
p2；//字符串2向右移动1位。
}
P1；//字符串1右移1位。
}
while(max-)//输出字符串
printf("%c "，* start)；
printf(" \ n ")；
}
寻找C语言中最长的公共子串长度 两个字符串组合成一个二维数组，相同的值为1，不同的值为0。同时在对角线上叠加，矩阵中的最大值就是最长的公共子串长度。
# # # # # # 3.编译源代码
c语言寻找最长的公共子串代码，包括一个j = length1不太明白功能是什么。没有这句话有什么影响？请回答。 这个算法是错误的。代码中有一些错误。我修改如下:
j =length的本意是在满足s[i]==t[j]时移动T串。
但是为什么可以一下子把长度移动这么长呢？这样，虽然程序不会无休止地循环，但结果是错误的。
因为一次移动太多，可能会错过真正最长的公共子串，比如下面的例子:
#包含stdio.h
#包含字符串. h
void MaxComStr_youError(char s[]，char t[]，char c[])
{
int index=0，长度=0，I，j，k，length 1；
I = 0；
while(s[i]！='\0')
{
j = 0；
while(t[j]！='\0')
{
if(s[i]==t[j])
{
length1 = 1
for(k = 1；I kstr len(s)j kstr len(t)s[I k]= = t[j k]；k)
长度1；
if(长度1长度)
{
index = I；
长度=长度1；
}
j =长度1；//这句话的作用是什么？这句话对节目有什么影响？×/
}
else j；
}
我；
}
for(I = 0；ilength我)
c[I]= s[索引I]；
c[length]= ' \ 0 '；
}
void MaxComStr_OK(char s[]，char t[]，char c[])
{
int index=0，长度=0，I，j，k，length 1；
I = 0；
while(s[i]！='\0')
{
j = 0；
while(t[j]！='\0')
{
if(s[i]==t[j])
{
length1 = 1
for(k = 1；I kstr len(s)j kstr len(t)s[I k]= = t[j k]；k)
长度1；
if(长度1长度)
{
index = I；
长度=长度1；
}
}
j；
}
我；
}
for(I = 0；ilength我)
c[I]= s[索引I]；
c[length]= ' \ 0 '；
}
int main(int argc，char* argv[])
{
char s[]= " xxxxxxxx ababc "；
char t[]= " abababc "；
char c[100]；
printf("s=%s\r\nt=%s\r\n "，s，t)；
MaxComStr_youError(s，t，c)；
printf(" \ r \ n错误结果:%s\r\n "，c)；
MaxComStr_OK(s，t，c)；
printf("OK结果:%s "，c)；
}
程序输出是:
s = xxxxxxxx xababc
t=abababc
错误结果:abab
OK结果:ababc
C语言中最长的公共子串 首先指出楼主的错误
最长的公共子串应该改为最长的连续公共子串。
以下是符合楼主要求的参考代码。
//作者:白哈克
//时间:2006年12月9日
#包含stdio.h
#包含字符串. h
void main()
{
char * x = " aabcdababce
char * y = " 12abcabcdace
int m = strlen(x)；
int n = strlen(y)；
int i，j，k，l；
int maxlength = 0；
int start = 0；
int count = 0；//用于判断是否匹配的变量。
for(I = 1；I = n；I )//匹配长度的循环
for(j = 0；jn-I 1；j )//y的开始位置的循环
for(k = 0；km-I 1；k )//x的循环起始位置
{
count = 0；
for(l = 0；李；L )//判断是否匹配，代码可以优化。
if (y[j l] == x[k l])
数数；
if (count==iimaxlength)
{
maxlength = I；//记录最大长度
start = j；//记录最大长度的起始位置
}
}
//作者:白哈克
//时间:2006年12月9日
#包含stdio.h
#包含字符串. h
void main()
{
char * x = " aabcdababce
char * y = " 12abcabcdace
int m = strlen(x)；
int n = strlen(y)；
int i，j，k，l；
int maxlength = 0；
int start = 0；
int count = 0；//用于判断是否匹配的变量。
for(I = 1；I = n；I )//匹配长度的循环
for(j = 0；jn-I；j )//y的开始位置的循环
for(k = 0；km-I；k )//x的循环起始位置
{
count = 0；
for(l = 0；李；L )//判断是否匹配，代码可以优化。
if (y[j l] == x[k l])
数数；
if (count==iimaxlength)
{
maxlength = I；//记录最大长度
start = j；//记录最大长度的起始位置
}
}
if (maxlength==0)
printf("无答案")；
其他
for(I = 0；imaxlength我)
printf("%c "，y[start I])；
}
}
下面是最长公共子串的真实动态规划算法。
//作者:白哈克
//时间:2006年12月9日
#包含stdio.h
#包含字符串. h
int b[50][50]；
int c[50][50]；
无效lcs，m，y，n)
char * x；
int m；
char * y；
int n；
{
int I；
int j；
for(I = 1；I = m；I)c[I][0]= 0；
for(I = 1；I = n；I)c[0][I]= 0；
c[0][0]= 0；
for(I = 1；I = m；我)
for(j = 1；j = n；j)
{
if (x[i-1] == y[j-1])
{
c[I][j]= c[I-1][j-1]1；
b[I][j]= 1；
}
其他
if (c[i-1][j] c[i][j-1])
{
c[I][j]= c[I-1][j]；
b[I][j]= 2；
}
其他
{
c[I][j]= c[I][j-1]；
b[I][j]= 3；
}
}
}
空显示(I，j，x)
int I；
int j；
char * x；
{
if (i==0||j==0)
返回；
if (b[i][j]==1)
{
show(i-1，j-1，x)；
printf("%c "，x[I-1])；
}
其他
if (b[i][j]==2)
show(i-1，j，x)；
其他
show(i，j-1，x)；
}
void main()
{
char * x = " aabcdababce
char * y = " 12abcabcdace
int m = strlen(x)；
int n = strlen(y)；
lcs(x，m，y，n)；
show(m，n，x)；
}
最后更新于 2023-10-07 22:01:56 并被添加「」标签，已有 位童鞋阅读过。
本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处
相关文章