Weighted LCS

wlcs.cc

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <stack>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <utility>
#include <tuple>
#include <queue>
#include <random>

using namespace std;

random_device rd;
default_random_engine rng(rd());
uniform_int_distribution<int> dist_letter(0, 25);
uniform_int_distribution<int> dist_w(-10, 10);

string gen(int len) {
  string str = "";
  while (len --) {
    str += char('a' + dist_letter(rng));
  }
  return str;
}

int weighted_lcs(const string& A, const string& B, const unordered_map<char, int>& w) {
  int n = A.size();
  int m = B.size();
  vector<vector<int>> F(n + 1, vector<int>(m + 1, 0));

  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j) {
      F[i][j] = max(F[i - 1][j], F[i][j - 1]);
      if (A[i - 1] == B[j - 1]) {
        F[i][j] = max(F[i][j], F[i - 1][j - 1] + w.at(A[i - 1]));
      }
    }
  }
  return F[n][m];
}

int foo(const string& A, const string& B, const unordered_map<char, int>& w) {
  int n = A.size();
  int m = B.size();
  vector<vector<int>> F(n + 1, vector<int>(m + 1, 0));

  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j) {
      if (A[i - 1] == B[j - 1]) {
        F[i][j] = F[i - 1][j - 1] + max(0, w.at(A[i - 1]));
      } else {
        F[i][j] = max(F[i - 1][j], F[i][j - 1]);
      }
    }
  }
  return F[n][m];
}

int bar(const string& A, const string& B, const unordered_map<char, int>& w) {
  int n = A.size();
  int m = B.size();
  vector<vector<int>> F(n + 1, vector<int>(m + 1, 0));

  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j) {
      if (A[i - 1] == B[j - 1] && w.at(A[i - 1]) > 0) {
        F[i][j] = F[i - 1][j - 1] + w.at(A[i - 1]);
      } else {
        F[i][j] = max(F[i - 1][j], F[i][j - 1]);
      }
    }
  }
  return F[n][m];
}


int foobar(const string& AA, const string& BB, const unordered_map<char, int>& w) {
  string A = "";
  for (char c : AA) {
    if (w.at(c) > 0) {
      A += c;
    }
  }
  string B = "";
  for (char c : BB) {
    if (w.at(c) > 0) {
      B += c;
    }
  }
  
  int n = A.size();
  int m = B.size();
  vector<vector<int>> F(n + 1, vector<int>(m + 1, 0));

  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j) {
      if (A[i - 1] == B[j - 1]) {
        F[i][j] = F[i - 1][j - 1] + w.at(A[i - 1]);
      } else {
        F[i][j] = max(F[i - 1][j], F[i][j - 1]);
      }
    }
  }
  return F[n][m];
}

bool run() {
  const string A = gen(400);
  const string B = gen(300);
  
  unordered_map<char, int> w;
  for (int c = 'a'; c <= 'z'; ++ c) {
    w[c] = dist_w(rng);
  }
 
  int ans = weighted_lcs(A, B, w);
  // int out = foo(A, B, w);
  // int out = bar(A, B, w);
  int out = foobar(A, B, w);

  if (ans != out) {
    cout << A << endl;
    cout << B << endl;
    for (int c = 'a'; c <= 'z'; ++ c) {
      cout << c << "->" << w[c] << endl;
    }
    cout << ans << " " << out << endl;
    return false;
  }
  return true;
}

int main(int argc, char* argv[]) {
  int count = 0;
  while (true) {
    if (!run()) break;
    ++ count;
    if (count % 10000 == 0) {
      cout << count << endl;
    }
  }
  return 0;
}