TopCoder SRM 698

DIV2 500

Problem Statement

Brutal force with LCS: this problem is easy if we can identify and transform the core matching algorithm it requires to LCS. Here two implementations of LCS are provided, one is through recursion the other is through explicitly maintaining a lookup table. For some reasons, the recursion solution time out on one system test.

using namespace std;

// This will get TLE on one system test..
int lcs(const string &s1, const string &s2, int m, int n) {
    if (m == 0 || n == 0) return 0;
    if ((s1[m - 1] == s2[n - 1]) && (m > 0 && n > 0))
        return 1 + lcs(s1, s2, m - 1, n - 1);
    else
        return max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
}

int lcs2(const string &s1, const string &s2, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; ++i){
        for (int j = 0; j <= n; ++j) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

class RepeatStringEasy {
public:
    int maximalLength(string s) {
        if (s.empty()) return 0;
        int ret = 0;
        for (int i = 0; i < s.size(); ++i) {
            string s1 = "", s2 = "";
            for (int m = 0; m <= i; ++m) s1 += s[m];
            for (int n = i + 1; n < s.size(); ++n) s2 += s[n];
            ret = std::max(ret, 2 * lcs2(s1, s2, (int)s1.size(), (int)s2.size()));
        }
        return ret;
    }
}