Ⅰ 用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);
}