字符串最长公共子串
㈠ 最长公共子串
又是楼主?好像这个问题已经回答过了
下面的程序是符合楼主要求的程序
//作者: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;
}