0

さて、私の問題は次のとおりです。指定された 2 つの文字列間のより大きなシーケンスのサイズを返す必要があります。

現時点での私のコード:

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")
  • TWO FOUR // 1 (文字「O」)
  • abracadabra open // 0 (なし)
  • ねえ、この Java はいいね Java は新しいパラダイム // 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 に答える