USACO Gold 2017 Open - Bovine Genomics

Solution 1

Official Analysis (with hashing)

Solution 2

Sort suffixes.

$\mathcal{O}(NM^2\log N)$ solution:

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!

using pi = pair<int, int>;
using pl = pair<ll, ll>;

$\mathcal{O}(NM^2)$ solution:

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!

using pi = pair<int, int>;
using pl = pair<ll, ll>;

Solution 3

Probably possible to pass solutions with worse complexities ...