# Longest Common Substring

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.

**Implementation in Java**

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

**Time Complexity**

O(m*n)

Found a mistake? Have a question or improvement idea?
Let me know.

Table Of Contents