字元串最長公共子串
㈠ 最長公共子串
又是樓主?好像這個問題已經回答過了
下面的程序是符合樓主要求的程序
//作者: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);
}
㈡ 求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);
}
㈤ 求兩個字元串最大公共子串問題
已改，看注釋
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#define MaxSize 100
typedef struct
{
char str[MaxSize] ;
int len ;
}SeqString ;
int SubSeqString( SeqString *Sub , SeqString S , int pos , int len )
{
int i ;
if( pos < 0 || pos > S.len || len > S.len - pos || len < 1 )
{
Sub -> len = 0 ;
return 0 ;
}
else
{
for( i = 0 ; i < len ; i ++ )
{
Sub -> str[i] = S.str[i+pos] ;
}
Sub->str[i] = '\0'; // 字元串結束
Sub -> len = len ;
return 1 ;
}
}
int MaxSameSeqString( SeqString S , SeqString T , SeqString *M )
{
int i , j , k , t , pos ;
int len = 0 , maxlen = 0 ;
for( i = 0 ; i < S.len ; i++ )
{
k = i ;
for( j = 0 ; j < T.len ; j++ )
{
t = j ;
len = 0; // len賦值0
if( S.str[i] == T.str[j] )
{
while( S.str[k++] == T.str[t++] )
len++ ;
if( maxlen < len )
{
maxlen = len ;
pos = i ;
}
}
}
}
if( maxlen >= 1 )
{
SubSeqString( M , S , pos , maxlen ) ; // 參數是maxlen，不是len
return 1 ;
}
return 0 ;
}
int main()
{
SeqString X , Y ;
SeqString *R = (SeqString*)malloc(sizeof (SeqString));
char a[MaxSize] , b[MaxSize] ;
scanf( "%s" , a ) ;
scanf( "%s" , b ) ;
int alen , blen ;
alen = strlen(a) ;
blen = strlen(b) ;
X.len = alen ;
Y.len = blen ;
strcpy( X.str , a ) ;
strcpy( Y.str , b ) ;
MaxSameSeqString( X , Y , R ) ;
printf("%s" , R -> str );
return 0 ;}
㈥ 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(" ");
}
㈦ PHP怎麼做出兩個字元串的最長公共子串
矩陣法
原理：字元串1：string1＝＇aabbccdd＇字元版串2：string2＝＇accbbcdd＇
用string1的每個字元與string2的每個字元相比較，相等寫權做1．不等寫作0，則 如下所示：
第一行：10000000
第二行：10000000
第三行：00011000
第四行：00011000
第五行：01100100
第六行：01100100
第七行：00000011
第八行：00000011
可以看到1的對角線連起來最長的那行就是所求字元串，即加刪除線的部分，可得到字元串bbc和cdd
㈧ 用C＋＋編程求兩個字元串的最長公共子串
很復雜的
㈨ 求兩個字元串最長公共子串，不能用字元串標准函數，使用C語言
||#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||==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);
}
㈩ 如何使用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;
}