Longest Common Substring

Dynamic Programming | Set 29 (Longest Common Substring)

Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.

public class GetCommonSubString {

	public static void main(String[] args) {

			System.out.println(getCommonSubString("abcdefg","bcd"));
			Stack<Integer> s1 = new Stack<Integer>();
	}

	static	int  getCommonSubString(String s1,String s2){
		int res = Integer.MIN_VALUE;
		
		int dp[][] = new int[s1.length()][s2.length()];
	
		
		for(int i = 0; i< s1.length(); i++){
			for(int j = 0;j < s2.length(); j++){
				if(s1.charAt(i) == s2.charAt(j)){
					 if(i == 0 || j ==0){
						 dp[i][j] = 1;
					 }else{
						 dp[i][j] =  dp[i-1][j-1] + 1;
					 }
					 if(dp[i][j] > res){
						 res = dp[i][j];
					 }
				}
			}
		}
		return res;
		
		
	}
	
}

 

 

http://www.geeksforgeeks.org/longest-common-substring/