最長公共字串
⑴ 如何尋找兩個字元串的最長公共部分
演算法：求兩個字元串的最長公共子串原理：（1）將連個字元串分別以行列組成一個矩陣。（2）。若該矩陣的節點對應的字元相同，則該節點值為1。（3）當前字元相同節點的值=左上角(d[i-1,j-1])的值+1，這樣當前節點的值就是最大公用子串的
⑵ C語言編程 查找兩字元串的最長公共子串 如"I am a student."與"R u a student"最長公共子串是"student"
//有個問題是,空格應該也算字元吧，所以沒考慮空格。就像你那個例子，最長公共字串應該是//「student」,包含空格.還有,就是我這個應該不是很好的方法，效率比較低，我是先讓串//1不動，串2先從第1個字元開始與串1比較，然後串2從第2個字元開始於串1比較，都比較完了，///串1向右挪動一個位置
#include<stdio.h>
intmain()
{
charstr1[100]={0},str2[100]={0};
printf("pleaseinputtwostrings: ");
gets(str1);//讀入字串
gets(str2);
char*p1=str1;//分別用來存str1和str2的當下比較位置
char*p2=str2;
intmax=0,num=0;//max存放比較後最長字串長度，num是這一輪比較公共字串長度
char*start;//存放最大串起始位置
while(*p1!=' ')//先是串1大循環
{
p2=str2;//p2是串2首地址
while(*p2!=' ')
{
char*begin=p1;//begin是串1當前比較位置
char*begin2=p2;//begin2是串2開始比較位置
num=0;//比較前初始化為0
while(*begin!=' '&&*begin2!=' ')//一輪新的比較
{
if(*begin==*begin2)//若相同，num++；
{num++;begin++;begin2++;}
elsebreak;
}
if(num>max)//若新比較出的字串更長，則替換max值和start內容
{max=num;
start=p1;}
p2++;//串2右移1位
}
p1++;//串1右移1位
}
while(max--)//輸出串
printf("%c",*start++);
printf(" ");
}
⑶ 尋找最長公共子串(高分)
我是北京某大學的學生，前天實習時完美解決了此題。
這里人多，我怕暴露了身回份
http://netalpha.javaeye.com/blog/340554
相對的，答如果您有另一題的編碼，就是解釋程序的，請務必告訴我。
現有一些由英文字元組成的大小寫敏感的字元串。編寫一個程序，找到一個最長的字元串x，使得：對於已經給出的字元串中的任意一個y, x或者是y的子串、或者x中的字元反序之後得到的新字元串是y的子串。
⑷ 求N個字元串的最長公共子串，N＜＝20，字元串長度不超過255。
用動態規劃顯然沒有那麼恐怖的內存……
只能枚舉了
#include <stdio.h>
#include <string.h>
#define MAXN 20
#define MAXL 256
int n;
int len[MAXN];
char str[MAXN][MAXL];
int match(char *s1,char *s2,int len)
{
while (len--)
{
if (*s1!=*s2) return 0;
s1++;
s2++;
}
return 1;
}
main()
{
int i,j;
int ans,ansi;
char line[100];
scanf("%d",&n);
gets(line);
for (i=0;i<n;i++)
{
gets(str[i]);
len[i]=strlen(str[i]);
}
ans=-1;
for (j=len[0];ans==-1 && j>0;j--)
for (i=0;ans==-1 && i+j-1<len[0];i++)
{
int flag1,k;
flag1=1;
for (k=1;flag1 && k<n;k++)
{
int flag2,s;
flag2=0;
for (s=0;!flag2 && s+j-1<len[k];s++)
if (match(str[0]+i,str[k]+s,j)) flag2=1;
if (!flag2) flag1=0;
}
if (flag1)
{
ans=j;
ansi=i;
}
}
if (ans==-1) puts("No common substrings!");
else
{
for (i=0;i<ans;i++) putchar(str[0][i+ansi]);
putchar('\n');
}
}
⑸ 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);
}
⑹ 求最長公共子串 遞歸寫的
//剛寫的!
publicclassStringTest{
publicstaticvoidmain(String[]args){
Strings1="321abcDEFG123456";
Strings2="45DEFG123489";
Stringstr=method(s1,s2,0,s2.length(),3>2);
System.out.println(" "+s1+" "+s2+" 最大公共子串=>"+str);
}
privatestaticStringmethod(Strings1,Strings2,intt,intw,booleanb){
if(t>=w)returnnull;
Stringstr=s2.substring(t,w);
if(s1.contains(str))
returnstr;
else
if(b)
returnmethod(s1,s2,++t,w,b=!b);
else
returnmethod(s1,s2,t,--w,b=!b);
}
}
⑺ 如何使用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;
}
⑻ 最長公共子串和最長公共子序列的區別
/* 目標：輸出兩個字元串的所有公共最長子序列
date: 09-11-26
BY: zggxjxcgx
演算法： 判斷較短串是否為較長串的子序列，如果是則得到結果；
否則，對較短串進行逐個字元刪除操作（將字元替換為'#'表示刪除）。
刪除操作用遞歸函數進行實現。每層遞歸刪除一個字元，
若刪除一個字元後未得到匹配子序列，則還原該字元所在位置。
第n層遞歸未找到匹配子序列，則將遞歸層數加1，重復刪除直到剩下空串。
*/
#include<stdio.h>
#include<string.h>
int dep=0; /* 較短串的長度 */
int depflag=0; /*下一步要探測的深度 */
int lastflag=0; /* 是否找到匹配子序列，1為找到 */
int count=0; /* 目標結果的個數 */
int mystrcmp(char *s1,char *s2) /* 判斷s2是否為 s1的子串 */
{ while(*s1 *s2)
if(*s2=='#') s2++;
else if(*s2 == *s1) { s1++; s2++; }
else s1++;
while(*s2=='#') s2++;
if(*s2=='\0') return 1;
return 0;
}
void pristr(char *str) /* 列印最長子序列 */
{ if(0==count++) printf("\n公共最長子序列：\n");
printf("%2d:",count);
while(*str)
{ if(*str!='#')
printf("%c",*str);
str++;
}
printf("\n");
}
/*遞歸函數求最長子序列。start 控制下一個要檢測的字元,deptemp控制遞歸的深度,first為's'表示第一層遞歸 */
int fun(char *str1,char *str2,char *start,int deptemp,char first)
{ int i=0,j=0;
char *s,cback;
do
{ s=start;
if('s'==first) deptemp=depflag; /* 在第一層設置遞歸深度 */
while(*s)
{ if(*s=='#') { s++; continue; }
cback=*s; *s='#'; /* 刪除當前字元*/
if(mystrcmp(str1,str2)) { pristr(str2); lastflag=1; } /*找到匹配，將lastflag設為1，在完成深度為deptemp+1的探測（找到所有匹配）後退出遞歸 */
else if(deptemp>0) fun(str1,str2,s+1,deptemp-1,'n'); /* 深度探測，s+1表示從下一個位置開始刪除 */
*s=cback; s++; /* 還原該位置的字元，以便下次進行探測 */
}
if('s'==first) ++depflag; /* 刪除depflag+1個字元還未找到，則遞歸深度加1 */
}while(depflag<dep-1 's'==first 0==lastflag); /* 第一層遞歸具有特殊意義，由三個變數標記是否第一層 */
if(lastflag) return 1; /* lastflag 為1 表示找到匹配子序列 */
return 0;
}
void main()
{ char *s1,*s2;
char st1[]="asfdebjewcwedwk";
char st2[]="sabscdkwss"; // kwfsa
if(strlen(st1)>strlen(st2)) s1=st1,s2=st2; /* 將s1設為較長的串 */
else s1=st2,s2=st1;
printf("\nstr1:%s\nstr2:%s\n",s1,s2);
dep=strlen(s2); /* 得到較短串的長度 */
if(mystrcmp(s1,s2)) pristr(s2);
else if(0==fun(s1,s2,s2,0,'s')) printf("\n沒有公共元素！\n");
// printf("%d\n",mystrcmp("afdebjewcwedw","abcdw#"));
}
⑼ 最長公共子串
又是樓主?好像這個問題已經回答過了
下面的程序是符合樓主要求的程序
//作者: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;//記錄最大長度的起起位置
}
}
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);
}
⑽ 求兩個輸入的字元串的最長公共子串
演算法：求兩個字元串的最長公共子串
原理：
（1） 將連個字元串分別以行列組成一個矩陣。
（2）。若該矩陣的節點對應的字元相同，則該節點值為1。
（3）當前字元相同節點的值 = 左上角(d[i-1, j-1])的值 +1，這樣當前節點的值就是最大公用子串的長。
(s2)bcde
(s1)
a0000
b1000
c0200
d0030
3. 結果：只需以行號和最大值為條件即可截取最大子串
C# code:
[csharp]view plainprint?
publicstaticstringMyLCS(strings1,strings2)
{
if(String.IsNullOrEmpty(s1)||String.IsNullOrEmpty(s2))
{
returnnull;
}
elseif(s1==s2)
{
returns1;
}
intlength=0;
intend=0;
int[,]a=newint[s1.Length,s2.Length];
for(inti=0;i<s1.Length;i++)
{
for(intj=0;j<s2.Length;j++)
{
intn=(i-1>=0&&j-1>=0)?a[i-1,j-1]:0;
a[i,j]=s1[i]==s2[j]?1+n:0;
if(a[i,j]>length)
{
length=a[i,j];
end=i;
}
}
}
returns1.Substring(end-length+1,length);
}