fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int longestCommonSubstring(string str1, string str2) {
  8.     int n = str1.length();
  9.     int m = str2.length();
  10.  
  11.     // Create a (n+1) x (m+1) DP table initialized to 0
  12.     vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
  13.  
  14.     int maxLength = 0;  // To store the length of the longest common substring
  15.  
  16.     // Fill the table
  17.     for (int i = 1; i <= n; ++i) {
  18.         for (int j = 1; j <= m; ++j) {
  19.             if (str1[i - 1] == str2[j - 1]) {
  20.                 // Characters match, extend the substring
  21.                 dp[i][j] = 1 + dp[i - 1][j - 1];
  22.                 maxLength = max(maxLength, dp[i][j]);
  23.             } else {
  24.                 // Characters don't match, reset
  25.                 dp[i][j] = 0;
  26.             }
  27.         }
  28.     }
  29.  
  30.     return maxLength;
  31. }
  32.  
  33. int main() {
  34.     string str1 = "abcdxyz";
  35.     string str2 = "xyzabcd";
  36.     cout << "Length of Longest Common Substring: " << longestCommonSubstring(str1, str2) << endl;
  37.     return 0;
  38. }
  39.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Length of Longest Common Substring: 4
https://ideone.com/JMxldr
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!