USACO 2.3 Longest Prefix

Typical dyanmic programming problem as the string matching can be broken into sub problems which overlap with each other.

Key observations:

• Let’s have dp[i] represents the longest possible prefix starting at index i, with i in the range of 0 to size - 1, with size being the length on the source string under match. The state transformation equation is: dp[i] = max(dp[i], dp[i] + j - i), if and only if substring starting from index i with length j - i is one of the dictionary string. With this, we search starting from the end of the string and once we finish, the answer would be dp[0].
• Compute the state transformation from end to start of string (as we are searching for longest prefix.).

Traps:

• The input string to match can span across multiple lines! So a single read will not possibly grab the entire source string; instead multiple reads might be required.
• The important constraint when matching against primitives: primitives are all in length 1..10. Without this constraints, it is very easy to get timeout error on the last test case.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <unordered_set>

using namespace std;
int main() {
    ifstream fin("prefix.in");
    ofstream fout("prefix.out");
    unordered_set<string> pset;

    string cur;
    fin >> cur;
    while (cur != ".") {
        pset.insert(cur);
        fin >> cur;
    }

    string s;
    while (!fin.eof()) {
        string str;
        fin >> str;
        s += str;
    }

    int size = (int)s.size();
    vector<int> dp(size, 0);
    if (pset.count(s.substr(size - 1))) {
        dp[size - 1] = 1;
    }

    for (int i = size - 1; i >= 0; --i) {
        for (int j = i + 1; j <= i + 10 && j < size; ++j) {
            string str = s.substr(i, j - i);
            if (pset.count(str)) {
                dp[i] = std::max(dp[i], dp[j] + j - i);
            }
        }
    }

    fout << dp[0] << endl;
}