USACO Gold 2017 Open - Bovine Genomics

Solution 1

Official Analysis (with hashing)

Solution 2

Sort suffixes.

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

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

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

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

Solution 3

Probably possible to pass solutions with worse complexities ...