developer033 developer033 - 7 months ago 16
Java Question

Return the size of the larger sequence between two given strings

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

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