「CF-633C」Spy Syndrome 2-Hash+map

#include <bits/stdc++.h>
typedef long long ll;
const ll p = 31;
std::string s;
std::map<ll, std::string> hash;
ll a[100100];
int n, m;
inline void print(int n) {
    if (!n) return;
    const std::string &str = hash[a[n]];
    print(n - str.size());
    std::cout << str << " ";
}
inline void solve() {
    ll h = 0;
    for (register int i = 0; i < m; i++) {
        std::string w;
        std::cin >> w;
        h = 0;
        for (register int j = 0; j < w.size(); j++) h = h * p + tolower(w[j]);
        hash[h] = w;
    }
    std::fill(a, a + n, -1);
    a[0] = 0;
    for (register int i = 0; i < n; i++) {
        h = 0;
        for (register int j = i; j >= 0; j--) {
            h = (h * p + s[j]);
            if (a[j] != -1 && hash.count(h)) {
                a[i + 1] = h;
                break;
            }
        }
    }
    print(n);
}
int main() {
    std::cin >> n >> s >> m;
    solve();
    return 0;
}