0

好吧，我的问题是：我必须返回两个给定字符串之间较大序列的大小。

我目前的代码：

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(
            new InputStreamReader(System.in));
    while (true) {
        String word1 = br.readLine();
        if (word1 == null) {
            break;
        }
        String word2 = br.readLine();
        int lengthWord1 = word1.length();
        int lengthWord2 = word2.length();
        int max = 0;
        if (word1.equals(word2) || word2.contains(word1)) {
            max = lengthWord1;
        } else if (word1.contains(word2)) {
            max = lengthWord2;
        } else {
            int j = 1;
            int maxLength = Math.max(lengthWord1, lengthWord2);
            int counter = 0;
            String largerWord;
            String smallestWord;
            if (maxLength == lengthWord1) {
                largerWord = word1;
                smallestWord = word2;
            } else {
                largerWord = word2;
                smallestWord = word1;
            }
            int minLength = smallestWord.length();
            int oldMax = 0;
            for (int i = 0; i < maxLength - 1; i++) {
                while (maxLength + 1 != j) {
                    String x = largerWord.substring(i, j++);
                    int lengthOfReplace = smallestWord 
                            .replace(x, "").length();
                    if (minLength == lengthOfReplace) {
                        if (max != 0) {
                            i = counter;
                            if (smallestWord.contains(
                                    x.substring(x.length() - 1))) {
                                i--;
                            }
                        }
                        break;
                    }
                    max = Math.max(minLength - lengthOfReplace, oldMax);
                    counter++;
                    oldMax = max;
                }
            }
        }
        System.out.println(max);
    }
}

一些输入及其预期输出：

  • abcdef cdofhij // 2 (对 ("cd")
  • 二四// 1（字母“O”）
  • abracadabra open // 0（无）
  • Hey This java is nice Java is a new patterns // 7 ("ava is ")

上面的所有输入都与我的代码完美配合，但在某些情况下仍然失败（可能是因为它有重复的字母，我不知道）..

错误输出示例：

  • abXabc abYabc // 它应该输出 3，但返回 4

所以，我现在被困住了，任何帮助表示赞赏。

4

1 回答 1

1

您正在寻找最长的公共子串问题

这是java中的代码

public static int longestSubstring(String str1, String str2)
{
    StringBuilder sb = new StringBuilder();
    if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty())
        return 0;

    // ignore case
    str1 = str1.toLowerCase();
    str2 = str2.toLowerCase();

    // java initializes them already with 0
    int[][] num = new int[str1.length()][str2.length()];
    int maxlen = 0;
    int lastSubsBegin = 0;

    for (int i = 0; i < str1.length(); i++)
    {
        for (int j = 0; j < str2.length(); j++)
        {
            if (str1.charAt(i) == str2.charAt(j))
            {
                if ((i == 0) || (j == 0))
                    num[i][j] = 1;
                else
                    num[i][j] = 1 + num[i - 1][j - 1];

                if (num[i][j] > maxlen)
                {
                    maxlen = num[i][j];
                    // generate substring from str1 => i
                    int thisSubsBegin = i - num[i][j] + 1;
                    if (lastSubsBegin == thisSubsBegin)
                    {
                        // if the current LCS is the same as the last time
                        // this block ran
                        sb.append(str1.charAt(i));
                    }
                    else
                    {
                        // this block resets the string builder if a
                        // different LCS is found
                        lastSubsBegin = thisSubsBegin;
                        sb = new StringBuilder();
                        sb.append(str1.substring(lastSubsBegin, i + 1));
                    }
                }
            }
        }
    }
    return sb.toString().length();
}
于 2016-04-23T01:28:24.727 回答