いい感じの Greedy 問題
問題概要
個の文字列
が与えられる。2 つの文字列
について、
の最後 i 文字と、
の最後 i 文字が共通
という条件を満たすとき、ラベル (i, c) をつけながら と
をマッチングすることができる。できるだけ多くのマッチングを作りたい。ただし、異なる 2 つのマッチング同士でラベルが同一になってはいけない。
例えば "AX", "BX", "CX, "DX" という 4 つの文字列からは "AX" と "BX" に対してラベル (1, 'X') をつけてマッチングすることができるが、残った "CX", "DX" に対しては (1, 'X') 以外のラベルでマッチさせることはできない。よって、マッチングできる文字列は最大 2 個だけである。
マッチングされる文字列の個数の最大値を求めよ。
制約
- テストケース数
考えたこと
基本的に Greedy にマッチングさせたくなる。このとき心配になるのは
a, b, c, d, があって、a と b、c と d がマッチングできるのに先に b と d をマッチングさせてしまったがために、残りの a と d をマッチングできない
みたいなことが発生しないかと心配になる。基本的には
- "PAXYZ"
- "QBXYZ"
とがあって、これを "XYZ" が共通ということから (3, 'X') とラベルをつけてマッチングするとき、"AXYZ" や "BXYZ" とが他の文字列と共通していなければ問題ない。具体的には "XYZ" が、マッチングさせたい文字列のペアの共通 suffix として考えられる最大長さであったならば大丈夫。
その場合は "AXYZ" がもし他の文字列と共通 suffix になるようなことがあれば、"AXYZ" が共通 suffix ということになって、"XYZ" が最大長さであることに矛盾する。
このことから、
- マッチングさせる suffix の長さが長い方から順に Greedy にマッチさせていく
という風にすれば大丈夫なことがわかる。Trie 木上で考えるとわかりやすい。なおここでは、各 i = 50, 49, ... について
- 残っている文字列に対して、後ろ i 文字分の suffix のローリングハッシュ値を求めて、そのハッシュ値ごとに個数を集計する
という実装にしてみた。
#include <iostream> #include <vector> #include <string> #include <set> #include <map> using namespace std; struct RollingHash { const int base = 9973; const vector<int> mod = {999999937LL, 1000000007LL}; string S; vector<long long> hash[2], power[2]; // construct RollingHash(){} RollingHash(const string &cs) { init(cs); } void init(const string &cs) { S = cs; int n = (int)S.size(); for (int iter = 0; iter < 2; ++iter) { hash[iter].assign(n+1, 0); power[iter].assign(n+1, 1); for (int i = 0; i < n; ++i) { hash[iter][i+1] = (hash[iter][i] * base + S[i]) % mod[iter]; power[iter][i+1] = power[iter][i] * base % mod[iter]; } } } // get hash of S[left:right] inline long long get(int l, int r, int id = 0) const { long long res = hash[id][r] - hash[id][l] * power[id][r-l] % mod[id]; if (res < 0) res += mod[id]; return res; } // get lcp of S[a:] and S[b:] inline int getLCP(int a, int b) const { int len = min((int)S.size()-a, (int)S.size()-b); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) / 2; if (get(a, a+mid, 0) != get(b, b+mid, 0)) high = mid; else if (get(a, a+mid, 1) != get(b, b+mid, 1)) high = mid; else low = mid; } return low; } // get lcp of S[a:] and T[b:] inline int getLCP(const RollingHash &t, int a, int b) const { int len = min((int)S.size()-a, (int)S.size()-b); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) / 2; if (get(a, a+mid, 0) != t.get(b, b+mid, 0)) high = mid; else if (get(a, a+mid, 1) != t.get(b, b+mid, 1)) high = mid; else low = mid; } return low; } }; void solve() { int N; cin >> N; vector<string> ss(N); for (int i = 0; i < N; ++i) cin >> ss[i]; // ロリハ vector<RollingHash> vr(N); for (int i = 0; i < N; ++i) vr[i].init(ss[i]); // まだマッチングされていない文字列の index の集合 set<int> se; for (int i = 0; i < N; ++i) se.insert(i); // 各文字 int res = 0; for (int len = 50; len > 0; --len) { map<long long, vector<int> > ma; for (auto i : se) { if (ss[i].size() < len) continue; int s = (int)ss[i].size(); long long hash = vr[i].get(s - len, s); ma[hash].push_back(i); } for (auto it : ma) { if (it.second.size() >= 2) { res += 2; int i = it.second.back(); se.erase(i); it.second.pop_back(); i = it.second.back(); se.erase(i); it.second.pop_back(); } } } cout << res << endl; } int main() { int T; cin >> T; for (int _ = 0; _ < T; ++_) { cout << "Case #" << _+1 << ": "; solve(); } }
