#include <iostream>
#include <vector>
#include <string>

std::size_t longest_common_subseq(const std::string& seq1, const std::string& seq2) {
  //std::vector<std::vector<int>> dp(seq1.size() + 1, std::vector<int>(seq2.size() + 1, 0));
  const int ROWS_COUNT = 2;
  std::vector<std::vector<int>> dp(ROWS_COUNT, std::vector<int>(seq2.size() + 1, 0));
  for (int i = 0; i < seq1.size(); ++i) {
    for (int j = 0; j < seq2.size(); ++j) {
      if (seq1[i] == seq2[j]) {
        //dp[i + 1][j + 1] = dp[i][j] + 1;
        dp[(i + 1) % 2][j + 1] = dp[i % 2][j] + 1;
      } else {
        //dp[i + 1][j + 1] = std::max(dp[i + 1][j], dp[i][j + 1]);
        dp[(i + 1) % 2][j + 1] = std::max(dp[(i + 1) % 2][j], dp[i % 2][j + 1]);
      }
    }
  }

  //return dp[seq1.size()][seq2.size()];
  return dp[seq1.size() % 2][seq2.size()];
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::string seq1;
  std::string seq2;

  std::cin >> seq1;
  std::cin >> seq2;

  auto len = longest_common_subseq(seq1, seq2);

  std::cout << len;

  return 0;
}