USACO 5.1 Musical Theme

If there is no constraint of the “transpose” (Transposed means that a constant positive or negative value is added to every note value in the theme subsequence), then the problem is obviously a string search problem. How to deal with transpose when doing string search?

• The property of transpose imply that if sequence A is a transpose of sequence B, then there must be that for every Ai, we have Ai + Diff = Bi. Similarly, Ai+1 + Diff = Bi+1.
• Now we have Ai+1 - Ai = Bi+1 - Bi.
• So the problem can be reduced again to plain sub string search problem: we just need to transform the input to a diff sequence by having each element a diff between two adjacent elements.
• For string search, use KMP so the time is linear.

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

using namespace std;

int ans = 0;
int N;
vector<int> str, table;

int main() {
    ifstream fin("theme.in");
    ofstream fout("theme.out");
    fin >> N;
    str = vector<int>(N + 1, 0);
    table = vector<int>(N + 1, 0);
    int prev = 0, cur;
    for (int i = 0; i < N; ++i) {
        fin >> cur;
        str[i] = cur - prev;
        prev = cur;
    }
    str[N] = prev * -1;
    for (int from = N - 5; from >= 5; --from) {
        std::fill(table.begin(), table.end(), 0);
        table[0] = table[1] = 0;
        for (int i = from + 1; i <= N; ++i) {
            int j = table[i - from];
            while (j > 0 && str[i] != str[from + j]) {
               j = table[j];
            }
            table[i - from + 1] = (str[i] == str[from + j]) ? j + 1 : 0;
        }
        int j = 0;
        for (int i = 0; i < from - 1; ++i) {
            while (j > 0 && str[i] != str[from + j]) {
                j = table[j];
            }
            if (str[i] == str[from + j]) {
                j++;
                ans = std::max(ans, j + 1);
            }
        }
    }
    
    cout << (ans < 5 ? 0 : ans) << endl;
    fout << (ans < 5 ? 0 : ans) << endl;
    return 0;
}