java基础知识回顾之---java String final类普通方法的应用之“两个字符串中最大相同的子串”

/*
 * 3,两个字符串中最大相同的子串。
 * "qwerabcdtyuiop"
 * "xcabcdvbn"
 *
 * 思路:
 * 1,既然取得是最大子串,先看短的那个字符串是否在长的那个字符串中。
 *   如果存在,短的那个字符串就是最大子串。
 * 2,如果不是呢,那么就将短的那个子串进行长度递减的方式取子串,去长串中判断是否存在。
 *   如果存在就已找到,就不用在找了。
 * 3.先找最大的子串,再递减子串找,找到,就停止
 */

原理图如图:

java基础知识回顾之---java String final类普通方法的应用之“两个字符串中最大相同的子串”

代码:

public class StringMax {

    /**
     * @param args
     */
    public static void main(String[] args) {

        String s1 = "qwerabcdtyuiop";
        String s2 = "xcabcdvbn";

        String s = getMax(s2, s1);
        System.out.println("s=" + s);
    }
    
    
    public static String getMax(String s1,String s2){
        //我们不知道S1,S2哪个大的情况下,判断并取出大的和小的
        String max,min = null;
        max = (s1.length() > s2.length()?s1:s2);
        min = max.equals(s1)?s2:s1;//如果大的与S1相等,就返回S2作为小的子符串
        for(int i=0;i<s1.length();i++){
            for(int a=0,b=s1.length()-i; b!=s1.length()+1;a++,b++){//从图中可以看到,a,b为字符串的量端,当len=8的时候,a=0,b=7;a=1,b=8
                String subStr = s1.substring(a,b);//len=8的时候子字符串为:xcabcdvb,cabcdvbn为两个
                if(s2.contains(subStr)){//判断大的字符串中是否包含子串
                    return subStr;
                }
            }
        }
        return null;
    }

    /**
     * 获取最大子串
     * 
     * @param s1
     * @param s2
     * @return
     */
    public static String getMaxSubstring(String s1, String s2) {
        
        String max = null,min = null;
        max = (s1.length()>s2.length())?s1:s2;//判断s1和s2哪个长,确定长的字符串和短的字符串
        min = max.equals(s1)?s2:s1;
        System.out.println("max="+max);
        System.out.println("min="+min);
        
        for (int i = 0; i < min.length(); i++) {
            
            for(int a = 0,b = min.length()-i; b != min.length()+1; a++,b++){//从大到小短的字符串递减
                
                String sub = min.substring(a, b);
                System.out.println(sub);//打印没每次内循环产生不同长度的子串
                if(max.contains(sub))//长的字符串是否包含短的子串
                    return sub;
            }
        }
        
        return null;
    }
}

 

java基础知识回顾之---java String final类普通方法的应用之“两个字符串中最大相同的子串”,布布扣,bubuko.com

java基础知识回顾之---java String final类普通方法的应用之“两个字符串中最大相同的子串”

上一篇:Spring源码阅读:Spring AOP设计与实现(一):动态代理


下一篇:DefaultNamespaceHandlerResolver中handlerMappings如何初始化