Return the size of the larger sequence between two given strings

Question

Well, my problem is: I have to return the size of the larger sequence between two given strings.

My code at the moment:

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);
    }
}

Some inputs and their expected outputs:

• abcdef cdofhij // 2 (Pair ("cd")
• TWO FOUR // 1 (Letter "O")
• abracadabra open // 0 (None)
• Hey This java is nice Java is a new paradigm // 7 ("ava is ")

All inputs above are working perfect with my code, but it's still failing in some cases (maybe because it has duplicate letters, I don't know)..

Example of incorrect output:

• abXabc abYabc // It should output 3, but returns 4

So, I'm stucked now, any help is appreciated.

Answer 1

You are looking for the Longest common substring problem

Here is the code in 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();
}