公共子串
Ⅰ 各位高手，怎么编找出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);
}
}
