Advertisement
Derga

Untitled

Sep 29th, 2020
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. // Space optimized CPP implementation of longest
  2. // common substring.
  3.  
  4. #include <vector>
  5. #include <string>
  6. #include <algorithm>
  7. #include <iostream>
  8.  
  9.  
  10. using namespace std;
  11.  
  12. // Function to find longest common substring.
  13. int LCSubStr(string X, string Y)
  14. {
  15.     // Find length of both the strings.
  16.     int m = X.length();
  17.     int n = Y.length();
  18.  
  19.     // Variable to store length of longest
  20.     // common substring.
  21.     int result = 0;
  22.  
  23.     // Matrix to store result of two
  24.     // consecutive rows at a time.
  25.     vector<vector<int>> len(2, vector<int>(n + 1));
  26.  
  27.     // Variable to represent which row of
  28.     // matrix is current row.
  29.     int currRow = 0;
  30.  
  31.     // For a particular value of i and j,
  32.     // len[currRow][j] stores length of longest
  33.     // common substring in string X[0..i] and Y[0..j].
  34.     for (int i = 0; i <= m; i++) {
  35.         for (int j = 0; j <= n; j++) {
  36.             if (i == 0 || j == 0) {
  37.                 len[currRow][j] = 0;
  38.             }
  39.             else if (X[i - 1] == Y[j - 1]) {
  40.                 len[currRow][j] = len[1 - currRow][j - 1] + 1;
  41.                 result = max(result, len[currRow][j]);
  42.             }
  43.             else {
  44.                 len[currRow][j] = 0;
  45.             }
  46.         }
  47.  
  48.         // Make current row as previous row and previous
  49.         // row as new current row.
  50.         currRow = 1 - currRow;
  51.     }
  52.  
  53.     return result;
  54. }
  55.  
  56. int main() {
  57.     short n;
  58.     cin >> n;
  59.  
  60.     string X;
  61.     for (int i = 0; i < n; ++i) {
  62.         short tmp;
  63.         cin >> tmp;
  64.         X.push_back(static_cast<unsigned char> (tmp));
  65.     }
  66.  
  67.     short k;
  68.     cin >> k;
  69.  
  70.     string Y;
  71.     for (int i = 0; i < k; ++i) {
  72.         short tmp;
  73.         cin >> tmp;
  74.         Y.push_back(static_cast<unsigned char> (tmp));
  75.     }
  76.  
  77.     cout << LCSubStr(X, Y);
  78.  
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement