公共子串
Ⅰ 各位高手，怎麼編找出N個字元串的公共子串
個人對編程有點愛好，就胡亂說些方案吧。
問題的意思是否是說從N個隨機的字元串中找出都包含的相同的子串，如下：ABCDSD,ASDCDAB,ADOABDCD3,AXDABCDSA,在這四個字元串中都包含有AB和CD，這個公共子串是否是自動查找？還是手動設定？這個相差很大。還有這個公共子串是否有長度限制，最少兩個字元？通過長度限制，從第一個字元串開始進行分解，遍歷N-1個字元串，然後如果每個字元串中都包含第一個字元串中分解出來的子串，則就找到一個，然後繼續分解完最後全部的排序。如ABCDSD，可以分解為AB,ABC,ABCD,ABCDS,ABCDSD五種子串。
當然，如果字元串的長度可以是隨機的，只需要找到長度最短的那個進行遍歷就可以了。
Ⅱ 求兩個輸入的字元串的最長公共子串
演算法：求兩個字元串的最長公共子串
原理：
（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);
}
Ⅲ 求助 公共子串
從公共串的第一個字母開始,查詢三個串,一旦發現全等則輸出,並開始確定公共串的下一個字母;當然還要避免重復
這是c語言的,運行沒問題
而且題目要求是50個字元以內,該演算法復雜度就在50^3即0.1M左右,不算大
#include <stdio.h>
#include <string.h>
#include <malloc.h>
//A,B,C分別表示輸入的三個串,R用來記錄一次公共子串
char A[51],B[51],C[51],R[51];
//LA,LB,LC分別表示ABC的字元串長,Num表示公共子串個數
int LA,LB,LC,Num;
//函數的功能:從A,B,C串的第sta,stb,stc位置開始
//查找相等項,查找成功則放入R串的level位置,並進而
//確認R串的下一位置level+1的應填入值
//查找會匹配三個串從sta,stb,stc開始的每個位置
void fun(int sta,int stb,int stc,int level)
{
//table是記錄該位置此字母出現過沒有
int *table=(int*)malloc(104);
int i,j,k;
memset(table,0,104);
//查詢三個串,尋找全等
for(i=sta;i<LA;i++)
for(j=stb;j<LB;j++)
for(k=stc;k<LC;k++)
if(A[i]==B[j]&&B[j]==C[k])
//如果字母沒出現過,則可以輸出
if(!table[A[i]-97])
{
R[level]=A[i];
//置表項字母為已出現
table[A[i]-97]=1;
puts(R);
Num++;
//開始確認下個字母
fun(i+1,j+1,k+1,level+1);
}
free(table);
R[level]=0;
}
main()
{
puts("輸入字元串");
scanf("%50s%50s%50s",A,B,C);
puts("________________");
LA=strlen(A),LB=strlen(B),LC=strlen(C);
//從三個串頭開始查找,首先確認的是R的第0位置
fun(0,0,0,0);
printf("公共子串有%d個",Num);
}
Ⅳ 數據結構求公共子串問題
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int main()
{
string str1,str2;
while (cin>>str1>>str2)
{
int m=str1.size(),n=str2.size();
int**ptr=new int*[m+1];
for (int i=0;i<=m;i++)
{
ptr[i]=new int [n+1];
}
for (int i=0;i<m;i++)
ptr[i][0]=0;
for (int i=0;i<n;i++)
ptr[0][i]=0;
for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
{
if(str1.at(i-1)==str2.at(j-1))
{ptr[i][j]=ptr[i-1][j-1]+1;cout<<ptr[i][j]<<ends;}
else
{ptr[i][j]=ptr[i-1][j]>ptr[i][j-1]?ptr[i-1][j]:ptr[i][j-1];cout<<ptr[i][j]<<ends;}
}
}
cout<<ptr[m][n]<<endl;
}
return 0;
}
用的是動態規劃的知識；
思想是這樣的：
Ⅳ 求兩個字元串最大公共子串問題
已改，看注釋
#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語言：「最長公共子串」 高手幫忙編個
描述]
現在有一些由英文字元組成的大小寫敏感的字元串，你的任務是找到一個最長的字元串[x]，使得對於已經給出的字元串中的任意一個y，[x]或[反序後的x]是y的子串。
[關於輸入]
輸入的第一行是一個整數t (1 <= t <= 10)，t表示測試數據的數目。對於每一組測試數據，第一行是一個整數n (1 <= n <= 100)，表示已經給出n個字元串。接下來n行，每行給出一個長度在1和100之間的字元串。
[關於輸出]
對於每一組測試數據，輸出一行，給出題目中要求的字元串x的長度。
Ⅶ 尋找最長公共子串(高分)
我是北京某大學的學生，前天實習時完美解決了此題。
這里人多，我怕暴露了身回份
http://netalpha.javaeye.com/blog/340554
相對的，答如果您有另一題的編碼，就是解釋程序的，請務必告訴我。
現有一些由英文字元組成的大小寫敏感的字元串。編寫一個程序，找到一個最長的字元串x，使得：對於已經給出的字元串中的任意一個y, x或者是y的子串、或者x中的字元反序之後得到的新字元串是y的子串。
Ⅷ 用C語言編寫求兩個字元串的公共子串！在線等！
靠，我們書上的例子。。
#include<stdio.h>
#include<string.h>
#define m 30
typedef struct
{char vec[m];
int len;
}orstr;
void maxstr(orstr *s1,orstr *s2)
{int index=0,long2=0,i,j,k,long1;
i=0;
while(i<s1->len)
{j=0;
while(j<s2->len)
{if(s1->vec[i]==s2->vec[j])
{long1=1;
for(k=1;s1->vec[i+k]==s2->vec[j+k];k++)long1=long1+1;
if(long1>long2)
{index=i;
long2=long1;
}
j+=long1;
}
else
j++;
}
i++;
}
printf("最長的公共子串:");
for(i=0;i<long2;i++)printf("%c",s1->vec[index+i]);
}
main()
{orstr *s1,*s2;
strcpy(s1->vec,"*******");//這里是要你輸入的字元串
s1->len=**;//這里要填你輸入的字元串個數
strcpy(s2->vec,"*******");//這里是要你輸入的字元串
s2->len=**;//這里要填你輸入的字元串個數
maxstr(s1,s2);
}
Ⅸ 最長公共子串
又是樓主?好像這個問題已經回答過了
下面的程序是符合樓主要求的程序
//作者: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);
}
Ⅹ 求最長公共子串 遞歸寫的
//剛寫的!
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);
}
}
