问题描述
网上都是动态规划。。但我要穷举法啊在键盘上输入三个字符串，然后输出最长公共子序列。。。【输入输出样例】输入：cecqbhvaiaedpibalukcabegviapcihlaaugckadceevfdadaepcialaukd输出：Cevapiluk都想到淘宝上买了。。。可是没有一个店家理我。。。救我。。。。。
解决方案
解决方案二：
你知道查下线段树算法。网上应该有现成的。
解决方案三：
穷举法是暴力法吗？这个运行起来够吃力啊。这是我写的暴力法。/**Tochangethislicenseheader,chooseLicenseHeadersinProjectProperties.*Tochangethistemplatefile,chooseTools|Templates*andopenthetemplateintheeditor.*/packagetest;importjava.util.ArrayList;importjava.util.List;/****@authorAdministrator*/publicclassSubString{/***@paramargsthecommandlinearguments*/staticbooleanisIn(Stringsub,StringIn){returnIn.contains(sub);}staticString[]getSubs(StringIn){char[]ins=In.toCharArray();intinL=(int)Math.pow(2,In.length());String[]asubs=newString[inL-1];Stringpositions;StringaSub;for(inti=1;i<inL;i++){positions=Integer.toBinaryString(i);if(positions.length()<ins.length){do{positions="0"+positions;}while(positions.length()<ins.length);}char[]aCs=positions.toCharArray();List<Character>aSubChars=newArrayList<Character>();for(intj=0;j<aCs.length;j++){if(Character.digit(aCs[j],10)==1){aSubChars.add(ins[j]);}}aSub=aSubChars.toString();asubs[i-1]=aSub;}returnasubs;}publicstaticvoidmain(String[]args){Stringa="dvsrwwwyui";Stringb="dvsrwwtyu";Stringc="dpseerwytiu";Stringmax=null;intmaxlength=0;String[]asubs=getSubs(a);String[]bsubs=getSubs(b);String[]csubs=getSubs(c);for(inti=0;i<asubs.length;i++){for(intj=0;j<bsubs.length;j++){for(intk=0;k<csubs.length;k++){if(asubs[i].equals(bsubs[j])&&asubs[i].equals(csubs[k])){if(csubs[k].length()>maxlength){maxlength=csubs[k].length();max=csubs[k];}}}}}if(max!=null){max=max.replace("[","").replace("]","").replace(",","").replace("","");}System.out.println(a);System.out.println(b);System.out.println(c);System.out.println("结果："+max);}}
dvsrwwwyuidvsrwwtyudpseerwytiu结果：dsrwyu
解决方案四：
抽屉原理，字母26个，每个字符串放入26个数组，最后被放了三次的就存在最长公共子序列
解决方案五：
本来不抱希望的。。。居然有人些了代码引用2楼skyhitnow的回复:
穷举法是暴力法吗？这个运行起来够吃力啊。这是我写的暴力法。/**Tochangethislicenseheader,chooseLicenseHeadersinProjectProperties.*Tochangethistemplatefile,chooseTools|Templates*andopenthetemplateintheeditor.*/packagetest;importjava.util.ArrayList;importjava.util.List;/****@authorAdministrator*/publicclassSubString{/***@paramargsthecommandlinearguments*/staticbooleanisIn(Stringsub,StringIn){returnIn.contains(sub);}staticString[]getSubs(StringIn){char[]ins=In.toCharArray();intinL=(int)Math.pow(2,In.length());String[]asubs=newString[inL-1];Stringpositions;StringaSub;for(inti=1;i<inL;i++){positions=Integer.toBinaryString(i);if(positions.length()<ins.length){do{positions="0"+positions;}while(positions.length()<ins.length);}char[]aCs=positions.toCharArray();List<Character>aSubChars=newArrayList<Character>();for(intj=0;j<aCs.length;j++){if(Character.digit(aCs[j],10)==1){aSubChars.add(ins[j]);}}aSub=aSubChars.toString();asubs[i-1]=aSub;}returnasubs;}publicstaticvoidmain(String[]args){Stringa="dvsrwwwyui";Stringb="dvsrwwtyu";Stringc="dpseerwytiu";Stringmax=null;intmaxlength=0;String[]asubs=getSubs(a);String[]bsubs=getSubs(b);String[]csubs=getSubs(c);for(inti=0;i<asubs.length;i++){for(intj=0;j<bsubs.length;j++){for(intk=0;k<csubs.length;k++){if(asubs[i].equals(bsubs[j])&&asubs[i].equals(csubs[k])){if(csubs[k].length()>maxlength){maxlength=csubs[k].length();max=csubs[k];}}}}}if(max!=null){max=max.replace("[","").replace("]","").replace(",","").replace("","");}System.out.println(a);System.out.println(b);System.out.println(c);System.out.println("结果："+max);}}dvsrwwwyuidvsrwwtyudpseerwytiu结果：dsrwyu
谢谢大神！！！本来不抱希望的55555555非常感谢
解决方案六：
为了防止被老师查到我得删除了
解决方案七：
引用4楼wushuangzhen的回复:
本来不抱希望的。。。居然有人些了代码Quote: 引用2楼skyhitnow的回复:
穷举法是暴力法吗？这个运行起来够吃力啊。这是我写的暴力法。/**Tochangethislicenseheader,chooseLicenseHeadersinProjectProperties.*Tochangethistemplatefile,chooseTools|Templates*andopenthetemplateintheeditor.*/packagetest;importjava.util.ArrayList;importjava.util.List;/****@authorAdministrator*/publicclassSubString{/***@paramargsthecommandlinearguments*/staticbooleanisIn(Stringsub,StringIn){returnIn.contains(sub);}staticString[]getSubs(StringIn){char[]ins=In.toCharArray();intinL=(int)Math.pow(2,In.length());String[]asubs=newString[inL-1];Stringpositions;StringaSub;for(inti=1;i<inL;i++){positions=Integer.toBinaryString(i);if(positions.length()<ins.length){do{positions="0"+positions;}while(positions.length()<ins.length);}char[]aCs=positions.toCharArray();List<Character>aSubChars=newArrayList<Character>();for(intj=0;j<aCs.length;j++){if(Character.digit(aCs[j],10)==1){aSubChars.add(ins[j]);}}aSub=aSubChars.toString();asubs[i-1]=aSub;}returnasubs;}publicstaticvoidmain(String[]args){Stringa="dvsrwwwyui";Stringb="dvsrwwtyu";Stringc="dpseerwytiu";Stringmax=null;intmaxlength=0;String[]asubs=getSubs(a);String[]bsubs=getSubs(b);String[]csubs=getSubs(c);for(inti=0;i<asubs.length;i++){for(intj=0;j<bsubs.length;j++){for(intk=0;k<csubs.length;k++){if(asubs[i].equals(bsubs[j])&&asubs[i].equals(csubs[k])){if(csubs[k].length()>maxlength){maxlength=csubs[k].length();max=csubs[k];}}}}}if(max!=null){max=max.replace("[","").replace("]","").replace(",","").replace("","");}System.out.println(a);System.out.println(b);System.out.println(c);System.out.println("结果："+max);}}dvsrwwwyuidvsrwwtyudpseerwytiu结果：dsrwyu
谢谢大神！！！本来不抱希望的55555555非常感谢
这段代码需要改进，改进交给你了。不要将三个字符串的所有子串都穷举出来，穷举一个就可以了，然后查看每个子串是否在其他两个串中。否则，算法复杂度是：O(2^(3*n)
解决方案八：
简单描述一下算法吧。找到三个个字符串的全部子序列，然后一一比较，这是上面的实现。找字符串子序列的算法：比如对于字符串avbcds,它的长度是7，那么它的子序列数量是2^7-1，对于其中每一个字母，要么选，要么不选，只有两种选择，所以7位，可能的组合就是2^7，减一是减去一种特殊情况，那就是全部不选的情况。怎么遍历呢？对于每一位做一个标记，选的话标为1，不选的话标为0，那么全不选表示为0000000,全选表示为1111111,因为全不选我们是不要的，所以，从0000001开始，这个数字表示的是只有s的串，因为只有最后一位是1，怎么从0000001到1111111全部遍历呢？其实这就是从1-2^7-1的遍历，把每个数字转成二进制就是上述的形式。显然，这些二进制数字都是不同的，而且全部遍历到了，那么，对应的字符串子串也全部穷举了。其实没必要三个子串都遍历，只要把第一个遍历后，在其他两个中查找有无就好了，过程中记下最长的输出来。这样，可以大幅度地降低算法复杂度，减少运行时间。