Ⅰ 用c语言编写一个函数，找出两个字符串的最大公共子字符串。
#include<stdio.h>
#include<string.h>
char *maxcommonstr(char *a,char *b);
int main()
{
char s[] = "abcabcdefabc";
char *d = "adcdef";
char *common=NULL;
common = maxcommonstr(s,d);
puts(common);
return 0;
}
char *maxcommonstr(char *a,char *b)
{
static char d[255] = {0};//存储最大公共字串
char temp[255]={0};//临时存储公共字串
char *p = NULL,*q = NULL,*r = NULL,*s =NULL;
while(*a)//从第一个字符开始遍历a串
{
p = a;//p指向a串
q = b;//q指向b串
r = temp;
for(s = q;s <= b +strlen(b); s ++)//从第一个字符开始遍历b串
{
q = s;
while( *p && *q && *p == *q )// 若相等则赋值后移指针
{
*r = *p;
p ++;
q ++;
r ++;
}
}
*r = '\0';//末尾手动补0
if(strlen(temp) > strlen(d)) //如果此趟字串比以记录最大字串长 则改变最大字串存储
strcpy(d,temp);
a++;// a串后移
}
return d;
}
仅供参考……
Ⅱ c语言找字符串最大公共字符串的程序,求改错
1for(i=maxlen,j=0;i<(maxlen+maxpos);i++,j++)
这一行复制的时候错了。。
应该是i=maxpos
2还有就是
for(k=1;(s1[i+k]==s2[j+k])&&(s1[i+k]!=0);k++)
这个s1[i+k]!=0应该是s1[i+k]!=' '
Ⅲ C语言程序：求两个字符串中的公共字符串个数及最大公共字符串
#include
#include
char
*maxcommonstr(char
*a,char
*b);
int
main()
{
char
s[]
=
"abcabcdefabc";
char
*d
=
"adcdef";
char
*common=null;
common
=
maxcommonstr(s,d);
puts(common);
return
0;
}
char
*maxcommonstr(char
*a,char
*b)
{
static
char
d[255]
=
{0};//存储最大公共字串
char
temp[255]={0};//临时存储公共字串
char
*p
=
null,*q
=
null,*r
=
null,*s
=null;
while(*a)//从第一个字符开始遍历a串
{
p
=
a;//p指向a串
q
=
b;//q指向b串
r
=
temp;
for(s
=
q;s
<=
b
+strlen(b);
s
++)//从第一个字符开始遍历b串
{
q
=
s;
while(
*p
&&
*q
&&
*p
==
*q
)//
若相等则赋值后移指针
{
*r
=
*p;
p
++;
q
++;
r
++;
}
}
*r
=
'\0';//末尾手动补0
if(strlen(temp)
>
strlen(d))
//如果此趟字串比以记录最大字串长
则改变最大字串存储
strcpy(d,temp);
a++;//
a串后移
}
return
d;
}
仅供参考……
Ⅳ n个字符串最大公共子串求解 C语言实现（n不固定）
首先我们把所有的字符串都链接起来，并且中间加上随意的不同间隔符，加这个是为了防止两个串连接起来对height数组造成影响。
然后我们只需要搞出来height数组。
然后我们需要二分一个答案即可。
验证这个答案是否合理的充要条件是存在一段连续的height值，使得这部分的所有height值均大于该答案。并且该部分包含了所有字符串。
包含该字符串的定义是该字符串有一个后缀存在于该部分中。
#include<cstdio>
#include<cstring>
#include<iostream>
usingnamespacestd;
intsum[1000001],rank[1000001],a[1000001],sa[1000001],trank[1000001],p,tsa[1000001],height[1000001];
intmini[200001][21],lg2[1000001],len,cond[1000001],tr[1000001],n,k,sta[1000001],end[1000001],cnt,belong[1000001];
intlast[1000001],leng[1000001];
longlongans[1000001];
charst[1000001];
voidgetrank(intn){
intm=200000;
for(inti=1;i<=n;i++)sum[rank[i]=a[i]]++;
for(inti=2;i<=m;i++)sum[i]+=sum[i-1];
for(inti=n;i>=1;i--)sa[sum[rank[i]]--]=i;
trank[sa[1]]=p=1;
for(inti=2;i<=n;i++){if(rank[sa[i]]!=rank[sa[i-1]])p++;trank[sa[i]]=p;}
for(inti=1;i<=n;i++)rank[i]=trank[i];
for(intj=1,m=p;j<n;j*=2,m=p){
p=0;
for(inti=n-j+1;i<=n;i++)tsa[++p]=i;
for(inti=1;i<=n;i++)if(sa[i]>j)tsa[++p]=sa[i]-j;
for(inti=1;i<=m;i++)sum[i]=0;
for(inti=1;i<=n;i++)sum[trank[i]=rank[i]]++;
for(inti=2;i<=m;i++)sum[i]+=sum[i-1];
for(inti=n;i>=1;i--)sa[sum[trank[tsa[i]]]--]=tsa[i];
trank[sa[1]]=p=1;
for(inti=2;i<=n;i++){
if((rank[sa[i-1]]!=rank[sa[i]])||(rank[sa[i-1]+j]!=rank[sa[i]+j]))p++;
trank[sa[i]]=p;
}
for(inti=1;i<=n;i++)rank[i]=trank[i];
}
}
voidgetheight(intn){
intk=0;
intpo1,po2;
for(inti=1;i<=n;i++){
po1=i,po2=sa[rank[i]-1];
if(k)k--;
while((a[po1+k]==a[po2+k])&&(po1+k<=n)&&(po2+k<=n))
k++;
height[rank[i]]=k;
}
}
intrmq(intl,intr){
intrang=(r-l+1),pow=lg2[rang];
return(min(mini[l][pow],mini[r-(1<<pow)+1][pow]));
}
intcheck(intpo,inthei){
if(po+hei-1>end[belong[po]])return(0);
intl=1,r=rank[po],L,R;
while(l<r){
intmid=(l+r)>>1;
if(rmq(mid+1,rank[po])>=hei)r=mid;elsel=mid+1;
}
L=l;
l=rank[po],r=len;
while(l<r){
intmid=(l+r+1)>>1;
if(rmq(rank[po]+1,mid)>=hei)l=mid;elser=mid-1;
}
R=l;
return(L<=cond[R]);
}
intlowbit(intpo){
return(po&(-po));
}
voidedi(intpo,intnum){
if(!po)return;
for(;po<=len;po+=lowbit(po))tr[po]+=num;
}
intquery(intpo){
intret=0;
for(;po;po-=lowbit(po))ret+=tr[po];
return(ret);
}
intmain(){
scanf("%d",&n);k=n;
for(inti=1;i<=n;i++){
scanf("%s",&st);
intlen=strlen(st);sta[i]=cnt+1;leng[i]=len;
for(intj=0;j<len;j++)a[++cnt]=st[j]-'a'+1,belong[cnt]=i;
end[i]=cnt;
a[++cnt]=26+i;
}
len=cnt;
getrank(len);getheight(len);
intnum=0,res=1;
for(inti=2;i<=len;i++){
if(i==res*2)num++,res*=2;
lg2[i]=num;
}
for(inti=1;i<=len;i++)mini[i][0]=height[i];
for(inti=1;i<=20;i++)for(intj=1;j<=len;j++)mini[j][i]=min(mini[j][i-1],mini[j+(1<<(i-1))][i-1]);
intpo=0;
for(inti=1;i<=len;i++){
if(belong[sa[i]]){
edi(last[belong[sa[i]]],-1);edi(i,1);
last[belong[sa[i]]]=i;
}
while(query(i)-query(po)>=k)po++;
cond[i]=po;
}
intnow=0,ans=0;
for(inti=1;i<=len;i++){
if(now)now--;
if(belong[i]){
while(check(i,now+1))
now++;
ans=max(ans,now);
}
}
printf("%d ",ans);
}
Ⅳ C语言题目：求两字符串中的最大公共字符串个数及公共字符串。 （不需要太过于繁琐，希望用最简单的方法）
devc的话，是有结果的，一按回车的话先出结果然后瞬间消失。在后面加一个函数就能保留结果查看了。
在后面加了gets（b）；然后就能用devc看到结果了。
#include<stdio.h>
int main()
{
char a[1024],b[1024],c[1024];/*定义三个字符数组a,b，c*/
int n=0;/*统计公共字符的个数*/
int i;
printf("input a:\n");
fflush(stdin);/*清空字符串*/
gets(a);
printf("input b:\n");
fflush(stdin);/*清空字符串*/
gets(b);
for(i=0;a[i]!='\0'&&b[i]!='\0';i++)
if(a[i]==b[i])
{
c[i]=a[i];/*把公共部分赋值给数组c[i]*/
n++;
}
c[i]=' ';
printf("公共部分的字符串个数是:\n");
printf("%d\n",n);
printf("公共部分的字符串:\n");
puts(c);
gets(b);
}
Ⅵ C语言：最大公共字符串求解
做项目也最怕遇到你这样的，需求不明确，你就问哪里有问题，根本不知道你什么意思，想表达什么
Ⅶ 如何使用C语言求解最长公共子字符串问题及相关的算法
假定字符串采用堆分配方式，编写一个程序，求两个字符串S和T的一个最长公共子串
本题的思路：
本题要实现的算法扫描两个字符串。其中index指出最长公共子串在s中的序号，length指出最长公共子串的长度
堆分配存储表示如下：
typedef struct{
char *ch;
int length;
}Hstring;
Status MaxComString(Hstring S,Hstring T,int &length){
index=0;
length=0;
i=0;
//令i作为扫描字符串S的指针
while(i<S.length){
j=0;
//令j作为扫描字符串T的指针
while(j<T.length){
if(s.ch[i]==T.ch[j]){
//找一个子串，其在字符串S中的序号为i，长度为length1
length1=i;
for(k=1;S.ch[i+k]==T.ch[j+k];k++)length1++;
if(length1>length){
//将较大长度值赋给index与length
index=i;
length=length1;
}
j=j+length1;//继续扫描字符串T中第j=length1个字符之后的字符
}else{
j++;
}
}//while
i++;
}//while
printf("最长公共子串:");
for(i=0;i<length;i++)printf("%c",S.ch[index+i]);
return OK;
}
Ⅷ 哎，一道求最长公共字符串的c语言题目，求解答。。我怎么这么弱呢
方法一：
Longest Common Substring和Longest Common Subsequence是有区别的
X = <a, b, c, f, b, c>
Y = <a, b, f, c, a, b>
X和Y的Longest Common Sequence为<a, b, c, b>，长度为4
X和Y的Longest Common Substring为 <a, b>长度为2
其实Substring问题是Subsequence问题的特殊情况，也是要找两个递增的下标序列
<i1, i2, ...ik> 和 <j1, j2, ..., jk>使
xi1 == yj1
xi2 == yj2
......
xik == yjk
与Subsequence问题不同的是，Substring问题不光要求下标序列是递增的，还要求每次
递增的增量为1， 即两个下标序列为：
<i, i+1, i+2, ..., i+k-1> 和 <j, j+1, j+2, ..., j+k-1>
类比Subquence问题的动态规划解法，Substring也可以用动态规划解决，令
c[i][j]表示Xi和Yi的最大Substring的长度，比如
X = <y, e, d, f>
Y = <y, e, k, f>
c[1][1] = 1
c[2][2] = 2
c[3][3] = 0
c[4][4] = 1
动态转移方程为：
如果xi == yj， 则 c[i][j] = c[i-1][j-1]+1
如果xi ! = yj, 那么c[i][j] = 0
最后求Longest Common Substring的长度等于
max{ c[i][j], 1<=i<=n， 1<=j<=m}
完整的代码如下：
/**
找出两个字符串的最长公共连续子串的长度
** author :liuwei
** data:2011-08-16
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int longest_common_substring(char *str1, char *str2)
{
int i,j,k,len1,len2,max,x,y;
len1 = strlen(str1);
len2 = strlen(str2);
int **c = new int*[len1+1];
for(i = 0; i < len1+1; i++)
c[i] = new int[len2+1];
for(i = 0; i < len1+1; i++)
c[i][0]=0;//第0列都初始化为0
for(j = 0; j < len2+1; j++)
c[0][j]=0;//第0行都初始化为0
max = -1;
for(i = 1 ; i < len1+1 ; i++)
{
for(j = 1; j < len2+1; j++)
{
if(str1[i-1]==str2[j-1])//只需要跟左上方的c[i-1][j-1]比较就可以了
c[i][j]=c[i-1][j-1]+1;
else//不连续的时候还要跟左边的c[i][j-1]、上边的c[i-1][j]值比较，这里不需要
c[i][j]=0;
if(c[i][j]>max)
{
max=c[i][j];
x=i;
y=j;
}
}
}
//输出公共子串
char s[1000];
k=max;
i=x-1,j=y-1;
s[k--]=' ';
while(i>=0 && j>=0)
{
if(str1[i]==str2[j])
{
s[k--]=str1[i];
i--;
j--;
}
else //只要有一个不相等，就说明相等的公共字符断了，不连续了
break;
}
printf("最长公共子串为：");
puts(s);
for(i = 0; i < len1+1; i++)//释放动态申请的二维数组
delete[] c[i];
delete[] c;
return max;
}
int main(void)
{
char str1[1000],str2[1000];
printf("请输入第一个字符串：");
gets(str1);
printf("请输入第二个字符串：");
gets(str2);
int len = longest_common_substring(str1, str2);
printf("最长公共连续子串的长度为：%d ",len);
system("pause");
return 0;
}
Ⅸ C语言中 什么是最大字符串
应该是按ASCII值进行排序，求得字符串中的字符按此排序规则是最大的。一般用strcmp()函数来实现。
如：world > hello
world > words
Ⅹ C语言 最长公共子串
首先指出楼主的错误
最长的公共子字符串 应该改成 最长的连续公共子字符串
下面是符合楼主要求的参考代码
//作者:hacker
//时间:9.12.2006
#include <stdio.h>
#include <string.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;j<n-i+1;j++)//y的起始位置的循环
for (k=0;k<m-i+1;k++)//x的起始位置的循环
{
count = 0;
for (l=0;l<i;l++)//判断是否匹配,代码可以优化
if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//记录最大长度
start = j;//记录最大长度的起起位置
}
}
//作者:hacker
//时间:9.12.2006
#include <stdio.h>
#include <string.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;j<n-i;j++)//y的起始位置的循环
for (k=0;k<m-i;k++)//x的起始位置的循环
{
count = 0;
for (l=0;l<i;l++)//判断是否匹配,代码可以优化
if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//记录最大长度
start = j;//记录最大长度的起起位置
}
}
if (maxlength==0)
printf("No Answer");
else
for (i=0;i<maxlength;i++)
printf("%c",y[start+i]);
}
}
下面是真正的最长公共子串的动态规划算法
//作者:hacker
//时间:9.12.2006
#include <stdio.h>
#include <string.h>
int b[50][50];
int c[50][50];
void lcs(x,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;i++)
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;
}
else
if (c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
void show(i,j,x)
int i;
int j;
char* x;
{
if (i==0||j==0)
return;
if (b[i][j]==1)
{
show(i-1,j-1,x);
printf("%c",x[i-1]);
}
else
if (b[i][j]==2)
show(i-1,j,x);
else
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);
}