求最大公串 两个字符串 求最大公串 急啊 相当急 只要代码ok？
得出两个字符串的最大公串，如“afegdajve” 和 “teeregdajp”的最大公串是 egdaj
问了好久了 也没有一个实实在在来点代码的 鄙视中
神马理论的 神马这个应该这样这样的
神马 先遍历 然后取最大公串 这类答复就不要上来了
一句话 只看代码 小弟急用 谢谢
高高在上的不愿意敲个代码给看的别发表评论了就 再次谢谢
非常谢谢 给力的来啊
小弟分不多 请见谅！！！！！！！！！！ --------------------编程问答--------------------
--------------------编程问答-------------------- http://topic.csdn.net/u/20120422/21/04688ff1-c4f1-4fce-82da-901c53950fd7.html?17074 --------------------编程问答-------------------- 以前帮别人写过，又改进了一点。。嘿嘿
public class Test {
public static void main(String[] args) {
String s1 = "afegdajve",s2="teeregdajp";
String smallStr,largeStr;
if(s1.length() > s2.length()){
smallStr = s2;
largeStr = s1;
}else {
smallStr = s1;
largeStr = s2;
}
String str;
int max = 0,count = 0;
String resultStr = null;
for(int i = 0;i < smallStr.length();i++){
str = String.valueOf(smallStr.charAt(i));
count = 0;
for(int j = i + 1;j < smallStr.length();j++){
if(largeStr.contains(str)){
count++;
if(count > max){
max = count;
resultStr = str;
}
str += String.valueOf(smallStr.charAt(j));
}
else {
break;
}
}
}
System.out.println("max same str : " + resultStr + " size : " + resultStr.length());
}
}
public class TestSequence{
public static void main(String args[]) {
String str1 = "afegdajve";
String str2 = "teeregdajp";
String temp = str1.length() > str2.length() ? str2 : str1;
String temp2 = temp == str1 ? str2 : str1;
int index2 = temp.length();
while (true) {
for (int i = 0;i+index2<temp.length();i++){
if (temp2.contains(temp.substring(i,i+index2))){
System.out.println(temp.substring(i,i+index2));
return;
}
}
index2--;
if(index2 == 0){
System.out.println("find nothing");
return;
}
}
}
}
--------------------编程问答-------------------- 这个是成熟的算法了
思路就是定一个2维数组，如
a f e g d a j v e
t 0 0 0 0 0 0 0 0 0
e 0 0 1 0 0 0 0 0 1
e 0 0 1 0 0 0 0 0 1
r 0 0 0 0 0 0 0 0 0
e 0 0 1 0 0 0 0 0 1
g 0 0 0 2 0 0 0 0 0
d 0 0 0 0 3 0 0 0 0
a 1 0 0 0 0 4 0 0 0
j 0 0 0 0 0 0 5 0 0
p 0 0 0 0 0 0 0 0 0
比如横向是字符串1，纵向是字符串2，然后按照2维数组遍历，如果某个位置的横向字符和纵向字符相同，则该位置的值等于其上一个对角位置的值加1，如上面的2，3，4，5，分别等于上一个对角位置的值+1，如果某个位置的横向和纵向字符串的值不同，则该位置的值为0
找到最大的值得位置，沿着其对角线，从1位置开始到最大值位置，分别取横向或纵向的字符组成字符串，就是最大相同的字串了
代码例子
public class Test {
public static void main(String[] args) throws Throwable {
String s1 = "afegdajve";
String s2 = "teeregdajp";
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int max = 0, row = 0, col = 0;
int[][] matrix = new int[c1.length+1][c2.length+1]; //定义2维数组
for (int i=1; i<matrix.length; i++) {
for (int j=1; j<matrix[i].length; j++) {
if (c1[i-1] == c2[j-1]) { //横向字符与纵向字符相同的时候
matrix[i][j] = matrix[i-1][j-1] + 1; //该位置的值等于上个对角位置的值加1
if (matrix[i][j] > max) {//跟踪最大值
max = matrix[i][j];
row = i;
col = j;
}
}
}
}
if (row >= max) { //如果找到字串
StringBuilder buf = new StringBuilder();
for (int i=row-max; i<row; i++) { //随便取横向或纵向的字符串都可以，这里取横向
//取纵向就是i从col-max到col位置
buf.append(c1[i]);
}
System.out.println(buf);
}
}
}
--------------------编程问答--------------------
写完帖子都有这么多回复了
--------------------编程问答--------------------
2楼那个对不住了 点错了非常感谢各位帮忙
我又找到一个短一些的 分享下
String a ="fegdajv";
String b ="teeregdajp";
for(char i :a.toCharArray() ){
if(b.indexOf(i)!=-1){
System.out.print(i);
}
}
再次感谢大家的解答 --------------------编程问答--------------------
这个能找公共子串？这个是找ab两个字符串中都有的字符吧，但是这些字符不连续的话就不是公共子串了
--------------------编程问答-------------------- --------------------编程问答--------------------
public static void main(String[] args) {
String s1 = "afegdajve";
String s2 = "teeregdajp"; // egdaj
String result = "";
String tmp = "";
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j <= s1.length(); j++) {
tmp = s1.substring(i, j);
if (s2.contains(tmp) && (tmp.length() > result.length())) {
result = tmp;
}
}
}
System.out.println(result);
}
--------------------编程问答--------------------
public static void main(String args[]) throws Exception{
String str1 = "asdeferdere";
String str2 = "cvvsdefrrt";
int m = str1.length();
int n = str2.length();
int maxLen = 0;
int sIndex = -1;
for(int i=0; (i+maxLen)<m ; i++){
int tmp = 0;
for(int j=0; j<n; j++){
if((i+tmp)<m && str1.charAt(i+tmp) == str2.charAt(j))
tmp++;
else{
if(tmp > maxLen){
maxLen = tmp;
sIndex = i;
}
tmp = 0;
}
}
}
}补充：Java , Java SE
