Q34 Longest Common Substring | Practice | GeeksforGeeks
Sun Mar 26 2023 13:09:31 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
//{ Driver Code Starts
//Initial Template for Java
import java.io.*;
import java.util.*;
class GFG
{
public static void main(String args[])throws IOException
{
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(read.readLine());
while(t-- > 0)
{
String input[] = read.readLine().trim().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
String S1 = read.readLine().trim();
String S2 = read.readLine().trim();
Solution ob = new Solution();
System.out.println(ob.longestCommonSubstr(S1, S2, n, m));
}
}
}
// } Driver Code Ends
//User function Template for Java
class Solution{
int longestCommonSubstr(String s1, String s2, int m, int n){
/* Q34 of dp playlist , compare all prefixes of both s1 and s2 and find longest
common suffix , that will become your longest common substring
*/
int dp[][] = new int[m+1][n+1];
int ans = 0;
//first coloumn and first row will be 0 , which is by default also 0
for(int i = 1 ; i < m+1 ; i++){
for(int j = 1 ; j < n+1; j++){
//if last chars are equal , ans = ansof(prefix) + 1 , ans of prefix
//can be found diagonally behind
if(s1.charAt(i-1) == s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
ans = Math.max(ans , dp[i][j]);
}
}
}
// for(int i = 0 ; i < m ; i++){
// for(int j = 0 ; j<n ; j++){
// System.out.print(dp[i][j] + " ");
// }
// System.out.println();
// }
return ans;
}
}
content_copyCOPY
https://practice.geeksforgeeks.org/problems/longest-common-substring1452/1
Comments