最长公共字串java代码 两个字符串最长公共子字符串java

java 两个字符串,求最长公共子串的长度

用动态规划最长公共字串java代码，

if (s1[i] == s2[j])

dp[i][j] = dp[i - 1][j - 1] + 1;

else

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

相关问答

Q1: 求两个字符串的最长公共子串，要求输入两个字符串，输出他们的最长公共子串，包括长度。

遍历一下就好了，java代码：

public class CommonSubString {

public String search(String s1,String s2)

{

String max = "";

for(int i=0; is1.length(); i++)

{

for(int j=i; js1.length(); j++)

{

String sub = s1.substring(i,j);

if((s2.indexOf(sub)!=-1)sub.length()max.length())

{

max = sub;

}

}

}

return max;

}

public static void main(String[] args)

{

String s1 = "abcdefghigj";

String s2 = "xyzabcdefigj";

String output = new CommonSubString().search(s1,s2);

System.out.println(output);

}

}

Q2: 寻找最长公共子串(高分)

小可来个最简练的。程序已加上注释并在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(kmax) /* 如果出现大于当前子串长度的子串，则替换子串位置和长度 */

{

index = j;

max = k;

}

}

for(i=0; imax; 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;in;i++)

fgets(str[i],N,stdin); /*用安全可靠的函数fgets()取代不安全的gets()函数*/

strcpy(str1,str[0]); /* str1初值为str[0] */

for(i=1;in;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;

}

Q3: java求最大公共子串

二楼改的

c = b.substring(i,j-1);

之后下标越界没了。

程序无法出结果，中间有死循环。当while语句执行完之后j是a.length();然后是执行内循环for语句for(j=b.length()-1;j0;j--) 此时只比较J0;。。。。好像是个死循环。最内层的循环可以在加一个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;im;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;km;k++) //求str数组的最大值

{

if(nummaxstr[k])

{

nummax=str[k];

}

}

for(k=0;km;k++)

if(nummax==str[k])

System.out.println(s2.substring(max[k]-str[k]+1,max[k]+1));

}

}

Q4: java怎么写求最长的公共子序列

/*目标：输出两个字符串的所有公共最长子序列date:09-11-26BY:zggxjxcgx算法：判断较短串是否为较长串的子序列，如果是则得到结果；否则，对较短串进行逐个字符删除操作（将字符替换为'#'表示删除）。删除操作用递归函数进行实现。每层递归删除一个字符，若删除一个字符后未得到匹配子序列，则还原该字符所在位置。第n层递归未找到匹配子序列，则将递归层数加1，重复删除直到剩下空串。*/#include#includeintdep=0;/*较短串的长度*/intdepflag=0;/*下一步要探测的深度*/intlastflag=0;/*是否找到匹配子序列，1为找到*/intcount=0;/*目标结果的个数*/intmystrcmp(char*s1,char*s2)/*判断s2是否为s1的子串*/{while(*s1*s2)if(*s2=='#')s2++;elseif(*s2==*s1){s1++;s2++;}elses1++;while(*s2=='#')s2++;if(*s2=='\0')return1;return0;}voidpristr(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'表示第一层递归*/intfun(char*str1,char*str2,char*start,intdeptemp,charfirst){inti=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的探测（找到所有匹配）后退出递归*/elseif(deptemp0)fun(str1,str2,s+1,deptemp-1,'n');/*深度探测，s+1表示从下一个位置开始删除*/*s=cback;s++;/*还原该位置的字符，以便下次进行探测*/}if('s'==first)++depflag;/*删除depflag+1个字符还未找到，则递归深度加1*/}while(depflagstrlen(st2))s1=st1,s2=st2;/*将s1设为较长的串*/elses1=st2,s2=st1;printf("\nstr1:%s\nstr2:%s\n",s1,s2);dep=strlen(s2);/*得到较短串的长度*/if(mystrcmp(s1,s2))pristr(s2);elseif(0==fun(s1,s2,s2,0,'s'))printf("\n没有公共元素！\n");//printf("%d\n",mystrcmp("afdebjewcwedw","abcdw#"));}

关于最长公共字串java代码和两个字符串最长公共子字符串java的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。