Longest Common Substring

Given two strings S1 and S2. Find the longest common substring between S1 and S2.
Example: S1 = "LCLC"  S2 = "CLCL"  LCS = "CLC"


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm Visualization




Code Snippet

			
package com.ideserve.virendra.questions;

import java.util.ArrayList;
import java.util.List;

public class LongestCommonSubstring {
	
	
	public static List<String> commonSubstring(String S1, String S2)
	{
		Integer match[][] = new Integer[S1.length()][S2.length()];
		
		int len1 = S1.length(); 
		int len2 = S2.length();
		int max = Integer.MIN_VALUE; //Maximum length of the string
		ArrayList<String> result = null; //Result list
		
		for(int i=0; i<len1; i++)
		{
			for(int j=0; j<len2; j++)
			{
				if(S1.charAt(i) ==  S2.charAt(j))
				{
					if ( i == 0 || j==0) 	match[i][j] = 1;
					
					else    match[i][j] = match[i-1][j-1] + 1;
					
					if(match[i][j] > max) //If you find a longer common substring re-initialize the max count and update the result list.
					{
						max =  match[i][j];
						result = new ArrayList<String>();
						result.add(S1.substring(i-max+1, i+1)); //substring starts at i-max+1 and ends at i
					}
					else if(match[i][j] == max) // else if you find a common substring with the max length, store it in the list.
					{
						result.add(S1.substring(i-max+1, i+1));
					}
				}
				else  match[i][j] = 0;

			}
		}
		return result;
	}
	
	
	public static void main(String args[])
	{
		List<String> result = commonSubstring("CLCL", "LCLC");
		for(String str: result)
		{
			System.out.println(str);
		}
	}

}
		

Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(n^2)


Contribution

  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.


    Virendra Karappa