CFR 633 C. Spy Syndrome 2 ( String hash + DP )

Problem - C - Codeforces
Reverse the text, and perform dynamic programming to mark if some index i is possible to be reached from some index j, and the word it should use to reach from j to i. Make use of Rabin-Karp hashing to accelerate word matching, overall complexity O( N * |W| ).

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1e4 + 4;
const int MAXM = 1e5 + 5;
const int MAXW = 1e3 + 3;

int n, m;
string t;
string w[ MAXM ];

typedef pair<int, ull> piu;
map<piu, int> dict;

int pre[MAXN];
piu usew[MAXN];

void solve(){
    for(int i = 0; i < m; ++i){
        ull hv = 0ULL;
        for(int j = 0; j < w[ i ].size(); ++j)
            hv = hv * 29 + tolower( w[ i ][ j ] ) - 'a';
        dict[ piu( w[ i ].size(), hv ) ] = i;
    }

    reverse( t.begin(), t.end() );
    memset( pre, -1, sizeof(pre) ); // -1: cannot
    for(int i = 0; i < n; ++i) if( i == 0 || pre[ i ] != -1 ){ // if pre[ i ] is a positive number, substring [ pre[ i ], i ) is in dict
        ull hv = 0ULL;
        for(int j = i; j - i + 1 <= 1000 && j < n; ++j){
            hv = hv * 29 + t[ j ] - 'a';
            if( dict.count( piu( j - i + 1, hv ) ) ){
                pre[ j + 1 ] = i;
                usew[ j + 1 ] = piu( j - i + 1, hv );
            }
        }
    }

    for(int u = n; u != 0; u = pre[ u ]){
        cout << w[ dict[ usew[ u ] ] ];
        if( pre[ u ] == 0 ) cout << endl;
        else cout << " ";
    }
}

int main(){
    ios::sync_with_stdio( false );
    cin >> n >> t;
    cin >> m;
    for(int i = 0; i < m; ++i)
        cin >> w[ i ];
    solve();
    return 0;
}