Created
March 29, 2018 03:31
-
-
Save avijitmondal/a8ac3677c4a6069f00e0a2cf4471206f to your computer and use it in GitHub Desktop.
Given 2 string str1 and str2 we have to find the length of the longest common substring between them. Examples Input : X = "abcdxyz", y = "xyzabcd" Output : 4 The longest common substring is "abcd" and is of length 4. Input : X = "zxabcdezy", y = "yzabcdezx" Output : 6 The longest common substring is "abcdez" and is of length 6.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public int getLongestCommonSubstring(String str1, String str2) { | |
| int arr[][] = new int[str2.length() + 1][str1.length() + 1]; | |
| int max = Integer.MIN_VALUE; | |
| for (int i = 1; i <= str2.length(); i++) { | |
| for (int j = 1; j <= str1.length(); j++) { | |
| if (str1.charAt(j - 1) == str2.charAt(i - 1)) { | |
| arr[i][j] = arr[i - 1][j - 1] + 1; | |
| if (arr[i][j] > max) | |
| max = arr[i][j]; | |
| } else | |
| arr[i][j] = 0; | |
| } | |
| } | |
| return max; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment