如何查找两个字符串中是否有相同的子串

Boolean bool = false; String a = "aldjfkld"; String b = "fjdkjfd"; int lena = a.length(); for(int i = 0; i < lena - 1; i++) { String c = a.substring(i, i + 2); int t = b.indexOf(c); if(t != -1) { bool = true; break; } } System.out.println(bool);

String a = "abcdefgh"; String b = "hijklmn"; boolean[][] grid = new boolean[26][26]; for(int i = 0; i < a.length() - 1; i++) grid[a.charAt(i) - 'a'][a.charAt(i + 1) - 'a'] = true; boolean found = false; for(int i = 0; i < b.length() - 1; i++) if(grid[b.charAt(i) - 'a'][b.charAt(i + 1) - 'a']) { found = true; } System.out.println(found);

/** * 比较两个字符串是否含有共同的子字符串 * @param str1 字符串一 * @param str2 字符串二 * @param includeSelf 子字符串是否包括本身 * @return 比较结果 */ public static boolean hasSameSubStr(String str1, String str2, boolean includeSelf) { String shortStr = str1.length() > str2.length()? str2: str1; String longStr = str1.length() > str2.length()? str1: str2; String temp = ""; for(int i = 0; i < shortStr.length(); i++) { for(int j = i + 2; j <= shortStr.length(); j++) { temp = shortStr.substring(i, j); if(includeSelf && longStr.indexOf(temp) > 0) { return true; } else if(!includeSelf && !temp.equals(shortStr) && longStr.indexOf(temp) > 0) { return true; } } } return false; }

/** * 比较两个字符串是否含有子字符串，如果有，获取最大的子字符串集合 * 返回值为List，长度为2，第一个元素为boolean型，表示是否含有子字符串，第二个元素为List<String>，表示最大子字符串的集合 * @param str1 字符串一 * @param str2 字符串二 * @param includeSelf 是否包括自身 * @return 比较结果 */ public static List<Object> compareStrWithSub(String str1, String str2, boolean includeSelf) { String shortStr = str1.length() > str2.length()? str2: str1; String longStr = str1.length() > str2.length()? str1: str2; String temp = ""; int subLength = 0; boolean hasSame = false; List<String> sameSubs = new ArrayList<String>(); List<Object> ret = new ArrayList<Object>(); for(int i = 0; i < shortStr.length(); i++) { for(int j = i + 2; j <= shortStr.length(); j++) { temp = shortStr.substring(i, j); boolean flag1 = includeSelf && longStr.indexOf(temp) > 0; boolean flag2 = !includeSelf && !temp.equals(shortStr) && longStr.indexOf(temp) > 0; if(flag1 || flag2) { hasSame = true; if(temp.length() > subLength) { sameSubs.clear(); sameSubs.add(temp); } else if(temp.length() == subLength) { sameSubs.add(temp); } subLength = temp.length(); } } } ret.add(hasSame); ret.add(sameSubs); return ret; }

/** * 获取两个字符串的最大的子字符串集合 * @param str1 字符串一 * @param str2 字符串二 * @param includeSelf 子字符串是否包括本身 * @return 最大的子字符串集合 */ public static List<String> getMaxSameSubStr(String str1, String str2, boolean includeSelf) { String shortStr = str1.length() > str2.length()? str2: str1; String longStr = str1.length() > str2.length()? str1: str2; String temp = ""; int subLength = 0; List<String> sameSubs = new ArrayList<String>(); for(int i = 0; i < shortStr.length(); i++) { for(int j = i + 2; j <= shortStr.length(); j++) { temp = shortStr.substring(i, j); boolean flag1 = includeSelf && longStr.indexOf(temp) > 0; boolean flag2 = !includeSelf && !temp.equals(shortStr) && longStr.indexOf(temp) > 0; if(flag1 || flag2) { if(temp.length() > subLength) { subLength = temp.length(); sameSubs.clear(); sameSubs.add(temp); } else if(temp.length() == subLength) { sameSubs.add(temp); } } } } return sameSubs; } /** * 比较两个字符串是否含有子字符串，如果有，获取最大的子字符串集合 * 返回值为List，长度为2，第一个元素为boolean型，表示是否含有子字符串，第二个元素为List<String>型，表示最大子字符串的集合 * @param str1 字符串一 * @param str2 字符串二 * @param includeSelf 是否包括自身 * @return 比较结果 */ public static List<Object> compareStrWithSub(String str1, String str2, boolean includeSelf) { String shortStr = str1.length() > str2.length()? str2: str1; String longStr = str1.length() > str2.length()? str1: str2; String temp = ""; int subLength = 0; boolean hasSame = false; List<String> sameSubs = new ArrayList<String>(); List<Object> ret = new ArrayList<Object>(); for(int i = 0; i < shortStr.length(); i++) { for(int j = i + 2; j <= shortStr.length(); j++) { temp = shortStr.substring(i, j); boolean flag1 = includeSelf && longStr.indexOf(temp) > 0; boolean flag2 = !includeSelf && !temp.equals(shortStr) && longStr.indexOf(temp) > 0; if(flag1 || flag2) { hasSame = true; if(temp.length() > subLength) { subLength = temp.length(); sameSubs.clear(); sameSubs.add(temp); } else if(temp.length() == subLength) { sameSubs.add(temp); } } } } ret.add(hasSame); ret.add(sameSubs); return ret; }

public class lcs { /** * @param args */ private static String string1 = "acdegfgggwwwww"; private static String string2 = "bcdefgggqq"; public static void searchlcs(char[] char1, char[] char2) { int[][] result = new int[char1.length+1][char2.length+1]; for(int i = 0; i < char1.length; i++) result[i][0] = 0; for(int j = 0; j < char2.length; j++) result[0][j] = 0; int maxLength = 0; int maxPosX = 0; int maxPosY = 0; for(int i = 0; i < char1.length; i++) for(int j = 0; j < char2.length; j++) if(char1[i] == char2[j]) { result[i+1][j+1] = result[i][j] + 1; if(result[i+1][j+1] > maxLength) { maxLength = result[i+1][j+1]; maxPosX = i+1; maxPosY = j+1; } } else result[i+1][j+1] = 0; System.out.print("maxLength: " + maxLength + " "); System.out.print("maxPos: " + maxPosX + ", " + maxPosY + " "); System.out.println(); for(int i = maxPosX - maxLength; i < maxPosX; i++ ) System.out.print(char1[i]); } public static void main(String[] args) { // TODO Auto-generated method stub char[] char1 = string1.toCharArray(); char[] char2 = string2.toCharArray(); searchlcs(char1, char2); } }

加为好友

发送私信

在线聊天

craky
狂人三号
等级:

发表于：2008-07-03 13:48:2215楼得分:10

[color=#FF00FF]郁闷疯掉，今天这是咋的了，这么简单个问题都搞错，我上面发的全不对，正确的如下[/color]

Java code


    /**
     * 比较两个字符串是否含有共同的子字符串
     * @param str1 字符串一
     * @param str2 字符串二
     * @param includeSelf 子字符串是否包括本身
     * @return 比较结果
     */
    public static boolean hasSameSubStr(String str1, String str2, boolean includeSelf)
    {
        String shortStr = str1.length() > str2.length()? str2: str1;
        String longStr = str1.length() > str2.length()? str1: str2;
        String temp = "";
        
        for(int i = 0; i < shortStr.length(); i++)
        {
            for(int j = i + 2; j <= shortStr.length(); j++)
            {
                temp = shortStr.substring(i, j);
                boolean flag1 = includeSelf && longStr.indexOf(temp) >= 0;
                boolean flag2 = !includeSelf && !temp.equals(shortStr) && longStr.indexOf(temp) >= 0;
                
                if(flag1 || flag2)
                {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    /**
     * 获取两个字符串的最大的子字符串集合
     * @param str1 字符串一
     * @param str2 字符串二
     * @param includeSelf 子字符串是否包括本身
     * @return 最大的子字符串集合
     */
    public static List<String> getMaxSameSubStr(String str1, String str2, boolean includeSelf)
    {
        String shortStr = str1.length() > str2.length()? str2: str1;
        String longStr = str1.length() > str2.length()? str1: str2;
        String temp = "";
        int subLength = 0;
        List<String> sameSubs = new ArrayList<String>();
        
        for(int i = 0; i < shortStr.length(); i++)
        {
            for(int j = i + 2; j <= shortStr.length(); j++)
            {
                temp = shortStr.substring(i, j);
                boolean flag1 = includeSelf && longStr.indexOf(temp) >= 0;
                boolean flag2 = !includeSelf && !temp.equals(shortStr) && longStr.indexOf(temp) >= 0;
                
                if(flag1 || flag2)
                {
                    if(temp.length() > subLength)
                    {
                        subLength = temp.length();
                        sameSubs.clear();
                        sameSubs.add(temp);
                    }
                    else if(temp.length() == subLength)
                    {
                        sameSubs.add(temp);
                    }
                }
            }
        }
        
        return sameSubs;
    }
    
    /**
     * 比较两个字符串是否含有子字符串，如果有，获取最大的子字符串集合
     * 返回值为List，长度为2，第一个元素为boolean型，表示是否含有子字符串，第二个元素为List<String>型，表示最大子字符串的集合
     * @param str1 字符串一
     * @param str2 字符串二
     * @param includeSelf 是否包括自身
     * @return 比较结果
     */
    public static List<Object> compareStrWithSub(String str1, String str2, boolean includeSelf)
    {
        String shortStr = str1.length() > str2.length()? str2: str1;
        String longStr = str1.length() > str2.length()? str1: str2;
        String temp = "";
        int subLength = 0;
        boolean hasSame = false;
        List<String> sameSubs = new ArrayList<String>();
        List<Object> ret = new ArrayList<Object>();
        
        for(int i = 0; i < shortStr.length(); i+