Manthan, Codefest 16 C: Spy Syndrome 2
解法
文字列の一致判定はローリングハッシュにしてもらって、メモ化再帰で計算量を減らす。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct ToLower { char operator()(char c) { return tolower(c); } }; class RollingHash { private: vector<long long> mod; void init() { // mod.push_back(999999937LL); mod.push_back(1000000009LL); } const long long base = 1000000007LL; int n; vector<vector<long long> > hs, pw; RollingHash() {} public: int cnt = 0; RollingHash(const string& s) : n(s.size()) { init(); hs.resize(mod.size()), pw.resize(mod.size()); for (int i = 0; i < mod.size(); i++) { hs[i].assign(n + 1, 0); pw[i].assign(n + 1, 0); hs[i][0] = 0; pw[i][0] = 1; for (int j = 0; j < n; j++) { // pw[i][j + 1] = pw[i][j] * base % mod[i]; // hs[i][j + 1] = (hs[i][j] * base + s[j]) % mod[i]; pw[i][j + 1] = pw[i][j] * base; hs[i][j + 1] = (hs[i][j] * base + s[j]); } } } inline long long hash(int l, int r, int i) { // return ((hs[i][r] - hs[i][l] * pw[i][r - l]) % mod[i] + mod[i]) % mod[i]; return hs[i][r] - hs[i][l] * pw[i][r - l]; } inline bool match(int l1, int r1, int l2, int r2) { bool ret = 1; for (int i = 0; i < mod.size(); i++) ret &= hash(l1, r1, i) == hash(l2, r2, i); return ret; } inline bool match(int l1, int l2, int k) { return match(l1, l1 + k, l2, l2 + k); } int lcp(int i, int j) { int l = 0, r = min(n - i, n - j) + 1; while (l + 1 < r) { int m = (l + r) / 2; if (match(i, i + m, j, j + m)) l = m; else r = m; } return l; } }; vector<int> dp; vector<bool> vis; vector<int> mapping; vector<int> T_size; vector<string> T; int N, M; bool dfs(RollingHash& lolita, int pos) { if (pos == N) return true; if (pos >= dp.size() || vis[pos]) return false; vis[pos] = true; for (int m = 0; m < M; ++m) { if (lolita.match(pos, mapping[m], T_size[m]) && dfs(lolita, pos + T_size[m])) { dp[pos] = m; return true; } } return false; } int main() { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> N >> S >> M; T.resize(M); T_size.resize(M); mapping.resize(M); for (size_t i = 0; i < M; i++) { cin >> T[i]; T_size[i] = T[i].size(); string t = T[i]; transform(t.begin(), t.end(), t.begin(), ToLower()); reverse(t.begin(), t.end()); S += "?"; mapping[i] = S.size(); S += t; } RollingHash lolita(S); dp.assign(N, -1); vis.assign(N, false); dfs(lolita, 0); for (int i = 0; i < N;) { if (i > 0) cout << " "; cout << T[dp[i]]; i += T_size[dp[i]]; } cout << endl; }