A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

Evangelvii

初级黑马

  • 黑马币:0

  • 帖子:8

  • 精华:0

© Evangelvii 初级黑马   /  2012-4-24 16:15  /  2155 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

找出两个字符串的最大公共子串,比如说s1="asdeferdere",s2="cvvsdefrrt"两者的最大公共子串为"sdef"
  1. import java.util.LinkedList;
  2. import java.util.List;

  3. public class Clothes {
  4.     public static void main(String[] args) {
  5.         String s2 = "45aefg1234";
  6.         String s1 = "12345aesadaefgfewfw";
  7.         zdggzc(s2, s1);
  8.     }

  9.     static void zdggzc(String s1, String s2) {
  10.         String temp;
  11.         if (s1.length() < s2.length()) {
  12.             temp = s1;
  13.             s1 = s2;
  14.             s2 = temp;
  15.             temp = null;
  16.         }
  17.         List<String> zdggzc = new LinkedList<String>();
  18.         int result = 0;
  19.         StringBuilder maxSubStr = new StringBuilder();

  20.         for (int i = 0; i <= s1.length() - 1; i++) {
  21.             char curChar = s1.charAt(i);
  22.             int indexInS2 = 0;
  23.             boolean flag = false;
  24.             while (true) {
  25.                 if (flag) {
  26.                     break;
  27.                 }
  28.                 if (indexInS2 > s2.length() - 1) {
  29.                     break;
  30.                 }
  31.                 indexInS2 = s2.indexOf(curChar, indexInS2);
  32.                 if (indexInS2 == -1) {
  33.                     break;
  34.                 }
  35.                 maxSubStr.append(curChar);
  36.                 int offInS1 = i;
  37.                 int offInS2 = indexInS2;
  38.                 while (true) {
  39.                     offInS1++;
  40.                     offInS2++;
  41.                     if (offInS1 > s1.length() - 1 || offInS2 > s2.length() - 1) {
  42.                         flag = true;
  43.                         break;
  44.                     }
  45.                     if (s1.charAt(offInS1) == s2.charAt(offInS2)) {
  46.                         maxSubStr.append(s1.charAt(offInS1));
  47.                     } else {
  48.                         indexInS2++;
  49.                         break;
  50.                     }
  51.                 }

  52.                 if (maxSubStr.length() >= result) {
  53.                     result = maxSubStr.length();
  54.                     zdggzc.add(maxSubStr.toString());
  55.                 }
  56.                 maxSubStr.delete(0, maxSubStr.length());
  57.             }
  58.         }
  59.         for (String string : zdggzc) {
  60.             System.out.println(string);
  61.         }
  62.     }
  63. }
复制代码
有没有简单的方法

1 个回复

倒序浏览
1。将长度较短作为参照,对其进行取子串,并将其子串在另一个字符串中进行匹配。
                从大往小取,长度依次递减。
        */
        public String getMaxString(String str1,String str2)
        {
                String max="";
                for(int x=0;x<str2.length();x++)
                {
                        String temp1=str2.substring(x);
                        for(int y=temp1.length();y>0;y--)
                        {
                                String temp2=temp1.substring(0,y);       
                                if((str1.indexOf(temp1))!=-1&&temp2.length()>max.length())
                                        max=temp2;
                        }       
                }
                return max;       
        }
        /*
        第二种方式。获取长度最大的子串,进行匹配,不满足,长度依次递次递增减减
        将每一次长度递减的子串全部取出进行匹配。
        */
        public String getMaxString_2(String str1,String str2)
        {
                for(int x=0;x<str2.length();x++)
                {
                        for(int y=0,z=str2.length()-x;z<=str2.length();y++,z++)
                        {
                                String temp=str2.substring(y,z);
                                if(str1.contains(temp))
                                        return temp;
                                //System.out.println(temp);       
                        }       
                }       
                return "";
        }
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马