klcsmemorized.cpp

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>

template <class T>
auto&& minusKFromAll(std::vector<T> v, T k) {
  std::transform(std::begin(v), std::end(v), std::begin(v), [](T i) { return i - 1; });

  return std::move(v);
}

int KLCSMemorized(std::vector<std::string> strings, 
                  std::vector<int> sizes, 
                  std::unordered_map<std::string, int>& lookup) {

  for(int i = 0; i < sizes.size(); i++) {
    if(sizes[i] == 0) {
      return 0;
    }
  }

  std::string key;
  for(const auto& len : sizes) {
    key += std::to_string(len) + "|";
  }

  if(lookup.find(key) == std::end(lookup)) {
    bool areEndsEqual = false;
    for(int i = 0; i < strings.size() - 1; ++i) {
      areEndsEqual = (strings[i][sizes[i]] == strings[i + 1][sizes[i + 1]]);
      if(!areEndsEqual) {
        break;
      } 
    }

    if(areEndsEqual) {
      lookup[key] = KLCSMemorized(strings, minusKFromAll<int>(sizes, 1), lookup) + 1;
    } else {
      std::vector<int> maxs;
      for(int i = 0; i < sizes.size(); i++) {
        auto newSizes = sizes;
        newSizes[i] -= 1;  
        maxs.push_back(KLCSMemorized(strings, std::move(newSizes), lookup));
      } 

      int maxLCS = *std::max_element(std::begin(maxs), std::end(maxs));

      lookup[key] = maxLCS;
    }
  }

  return lookup[key];
}

int main() {
  std::string s1 = "ABCBDAB";
  std::string s2 = "BDCABA";
  std::string s3 = "BADACB";

  std::vector<std::string> v;
  v.push_back(s1);
  v.push_back(s2);
  v.push_back(s3);

  std::vector<int> s;
  for(int i = 0; i < v.size(); ++i) {
    s.push_back(v[i].size());
  }

  std::unordered_map<std::string, int> lookup;
  int len = KLCSMemorized(v, s, lookup);
  std::cout << "len: " << len << std::endl;
}