Manthan, Codefest 16 C. Spy Syndrome 2

問題

codeforces.com

解法

準備として, 各文字列 wi を反転させて, 小文字化します。

やりたいことは, dp[now] = (now 文字目以降を wi を使って表現できるか？)
というものです。ただ, あとで dp 復元するために, dp[now] = (now 文字目から復元が不可能なら -2, そうでないなら now に到達する前に使った文字列 wp に対して p を返す) とします。

文字列 wi の長さが 1000 以下で, 与えられる暗号文の長さは 10000 なので, now から k 文字が wi で表現されるかを高速で求められればハッピーですが, これを実現するためにローリングハッシュを使いましょう。

[now, now+k-1] のハッシュ値は O(1) で求められ, wi のハッシュ値に対して二分探索(lower_bound)すれば O(log m) でこれは判定できます。

struct RollingHash {
    static const ll mul0=10009,mul1=10007;
    static const ll add0=1000010007, add1=1003333331;
    string s; int l;
    vector<ll> hash_,pmo_;
    void init(string s) {
        this->s=s; l=s.size();
        hash_.resize(l+1); pmo_.resize(l+1);
        hash_[0]=0; pmo_[0]=1;
        for (int i = 0; i < l; i++) pmo_[i+1]=pmo_[i]*mul0;
        for (int i = 0; i < l; i++) hash_[i+1]=(hash_[i]*mul0+add0+s[i]);
    }
    ll hash(int l,int r) { // s[l..r]
        return hash_[r+1]-hash_[l]*pmo_[r+1-l];
    }
};

RollingHash rhs;
vector<pair<ll, int> > revW;
int dp[10010];
int n;

int dfs(int now, int prev) {
    int& ret = dp[now];
    if (ret != -1) return ret;
    if (now == n) return dp[now] = prev;
    for (int w = 1; w <= min(1000, n-now); w++) {
        ll h = rhs.hash(now, now+w-1);
        auto it = lower_bound(revW.begin(), revW.end(), make_pair(h, -1));
        if (it->first == h) {
            if (dfs(now+w, it->second) >= 0) {
                return dp[now] = prev;
            }
        }
    }
    return dp[now] = -2;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    string s;
    cin >> s;
    rhs.init(s);
    int m;
    cin >> m;
    vector<string> w(m);
    revW.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> w[i];
        revW[i].second = i;
        string rev = w[i];
        reverse(rev.begin(), rev.end());
        for (char& c : rev) {
            if ('A' <= c && c <= 'Z') {
                c = (char)('a' + (c-'A'));
            }
        }
        RollingHash tmp;
        tmp.init(rev);
        int len = rev.size();
        revW[i].first = tmp.hash(0, len-1);
    }
    sort(revW.begin(), revW.end());
    memset(dp, -1, sizeof(dp));
    dfs(0, -1);
    vector<int> hoge;
    int cur = n;
    while (cur > 0) {
        hoge.push_back(dp[cur]);
        cur = cur-w[dp[cur]].size();
    }
    reverse(hoge.begin(), hoge.end());
    for (int el : hoge) cout << w[el] << " ";
    cout << endl;
    return 0;
}