Даны две строки. Задача состоит в том, чтобы найти длину самой длинной общей подстроки.
Пример 1:
Input: S1 = "ABCDGH", S2 = "ACDGHR", n = 6, m = 6
Output: 4
Explanation: The longest common substring
is "CDGH" which has length 4.
Обычная самая длинная общая подстрока требует небольшой модификации
потому что мы пытаемся найти последовательные последовательности, которые совпадают.
Итак, dp[i][j] = 1+ dp[i-1][j-1]; если символы с индексами i и j совпадают в обеих строках.
Для большей ясности обратитесь к этой ссылке
//User function Template for Java
class Solution{
int longestCommonSubstr(String S1, String S2, int n, int m){
//we will use same approach that we used in longest common subsequence
//with slight modification
int dp[][] = new int[n+1][m+1];// 1 based indexing
//base cased
//since its 0 based indexing first row and first column will have 0 values
//top down approach
for(int i =0;i<=n;i++){
dp[i][0] = 0;
}
for(int j=0;j<=m;j++){
dp[0][j] = 0;
}
int ans = 0;
for(int i=1;i<=n;i++){
for(int j =1;j<=m;j++){
if(S1.charAt(i-1)==S2.charAt(j-1)){
dp[i][j] = 1 + dp[i-1][j-1];
ans = Integer.max(dp[i][j],ans);
}
else dp[i][j] =0;
}
}
return ans;
}
}