① 两个字符串的所有公共最长子序列
/* 目标：输出两个字符串的所有公共最长子序列
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#"));
}
② 如何使用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;
}
③ 寻找最长公共子串(高分)
小可来个最简练的。程序已加上注释并在vs2005和dev-c++下严格验证通过。
程序已做修改，对多个字符串求最长公共子串。思路和求两个字符串公共子串相似。原因是：多个字符串的公共子串首先必须是任何两个字符串的公共子串。所以只需要先求出两个字符串的最长公共子串然后用此子串再和其他字符串再求最长公共子串，最后的最长公共子串即是结果。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int N = 1024;
const int M = 256;
void MaxSubString(char* str1,char* str2,char* s)
{
int i, j, k, index, max=0;/* 公共子串长度初始化为0 */
for(i=0; str1[i]; i++)
for(j=0; str2[j]; j++)
{
for(k=0; str1[i+k]==str2[j+k] && (str2[j+k] || str1[i+k]); k++)
; /* 此循环求公共子串的长度，长度为k */
if(k>max) /* 如果出现大于当前子串长度的子串，则替换子串位置和长度 */
{
index = j;
max = k;
}
}
for(i=0; i<max; i++)
s[i] = str2[index++];/* 求出最长公共子串 */
s[i]='\0';
}
int main(void)
{
int i,n;
char str[M][N],str1[N],s[N]; /* s[N]保存最长公共子串 */
while(1)
{
puts("Please input the number of strings:");
if(scanf("%d",&n)==1) /*剔除输入格式错误并输入字符串个数n*/
break;
fflush(stdin); /*清键盘缓冲区*/
}
fflush(stdin); /*由于下面fgets()函数和gets()函数一样是从键盘缓冲区取得字符，故这里先清空键盘缓冲区，否则会少一次输入*/
printf("Please input %d strings:\n",n); /* 输入n个字符串 */
for(i=0;i<n;i++)
fgets(str[i],N,stdin); /*用安全可靠的函数fgets()取代不安全的gets()函数*/
strcpy(str1,str[0]); /* str1初值为str[0] */
for(i=1;i<n;i++)
{
MaxSubString(str1, str[i],s);/* 两两字符串找最长公共子串 */
strcpy(str1,s);/* s复制给str1再找 */
}
printf("MaxSubString: %s\n",s);/* 打印出最长公共子串 */
printf("length=%d\n",strlen(s)); /* 打印出最长公共子串长度 */
system("pause");
return 0;
}
④ C语言实现最长公共子串与最长公共子序列
给定两个字符串s1="GeeksforGeeks"，s2="GeeksQuizGo"，则它们的最长公共子串为“Geeks”，长度为5。
运用动态规划的思想，将两个字符串映射为一张二维表，表格中的值代表到当前为止的最长公共子串的值，如下图所示：
生成这张表的步骤（假设这张表为t[][], r为行标，c为列标）：
Code
整个算法的时间复杂度为O(len1 * len2)，len1与len2分别为两个字符串的长度。
最长公共子序列与最长公共子串的区别是，最长公共子序列不要求“连续匹配”，它的目的是找到两个字符串中最大的公共部分。依然以s1="GeeksforGeeks"，s2="GeeksQuizGo"为例，它们的最长公共子序列为“Geekso”和“GeeksG”，长度为6。
它的二维表如下所示：
它的生成步骤与最长公共子序列的最大不同在第3步，最长公共子序列在遇到s1[r] != s2[c]情况时，不会将t[r][c]重置为0，而是选择Max(t[r-1][c], t[r][c-1])作为新值，即它一直保存着前面已比较序列的最长公共序列值。
⑤ 最长公共子串
找出 最长、连续的 子字符串
遍历X、Y的所有子字符串，找出 最长公共后缀 ，则最长公共后缀的长度就是最长公共子串的长度。
LCSSuffix[i][j] = LCSSuffix[i - 1][j - 1] + 1 （若X[i - 1] == Y[j - 1]）
0 （若X[i - 1] != Y[j - 1]）
打印最长递增子序列的版本
O(nlogn)算法复杂度的版本
定义数组outputList[A.length]，outputList[i]表示所有长度为i+1的递增子序列的最小尾元素。
容易证明：outputList[]是一个递增数组。
⑥ 寻找字符串数组的最长公共子串
所谓最长公共子串问题是寻找两个或多个已知字符串最长的子串。例如字符串 “ABCD”与“ABCDE”、“FABCDE”的最长公共子串是“ABCD”……
值得注意的是，有些人把最长公共子序列、最长公共前缀与最长公共子串搞混淆了，请特别注意⚠️。
《高效算法：竞赛、应试与提高必修128例》中介绍了最长公共子串的算法，不过只是找两个字符串之间的最长公共子串， 并没有给出任意个数 （此处当然指的是3个或以上）字符串的最长公共子串的求法。
现在用Python试写如下：
最长子串还可以用lamada写法，看起来更加简洁
这个方法的复杂度是 O(n1 x n1 x (n1 + ... + nK)) ， 如果字符串不复杂，还是可以一用的😄。
⑦ 最长公共子串
又是楼主?好像这个问题已经回答过了
下面的程序是符合楼主要求的程序
//作者: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：abcde
字符串2：abcdfe
那么：
最长公共子串：abcd
最长公共子序列：abcde
就是公共子串，必须在待匹配字符串中连续，而公共子序列只需要相对顺序匹配就行。
前者一般用KMP算法，后者一般用动态规划解决吧。
⑨ java求最大公共子串
二楼改的
c = b.substring(i,j-1);
之后下标越界没了。
程序无法出结果，中间有死循环。当while语句执行完之后j是a.length();然后是执行内循环for语句for(j=b.length()-1;j>0;j--) 此时只比较J>0;。。。。好像是个死循环。最内层的循环可以在加一个int k来控制。多次运行导致cpu上升至100%的。
提供一种矩阵算法，这是LCS的一种算法：
public class stringCompare {
/**求最长匹配子字符串算法
str数组记录每行生成的最大值strmax
max数组记录str数组最大时所处的列号nummaxj
最大子字符串为substring(nummax-strmax+1,strmax+1)
*/
public static void main(String[] args) {
String s1="asdfgxxcvasdfgc";
String s2="asdfxxcv";
int m=s1.length();
int n=s2.length();
int k=0;
int nummax=0;
int []str=new int[m];
int []max=new int[m];
int []num=new int[m];
for(int i=0;i<m;i++) //生成矩阵数组
for(int j=n-1;j>=0;j--)
{
if(s1.charAt(i)==s2.charAt(j))
if(i==0||j==0)
{
num[j]=1;
max[i]=j;
str[i]=1;
}
else
{
num[j]=num[j-1]+1;
if(max[i]<num[j])
{
max[i]=j;
str[i]=num[j];
}
}
else
num[j]=0;
}
for(k=0;k<m;k++) //求str数组的最大值
{
if(nummax<str[k])
{
nummax=str[k];
}
}
for(k=0;k<m;k++)
if(nummax==str[k])
System.out.println(s2.substring(max[k]-str[k]+1,max[k]+1));
}
}