Codeforces Round #338 (Div. 2) C. Running Track

,

落とした。 制約がそこまで大きくないこととdiv2のcであることから、string.substr等を使った$O(n^3)$を投げたら通ったりすると踏んで投げてみたらpretestで落とされ、 rolling hashとunordered_map.operator []を使って$O(n^2)$に落としたはずのものを投げたら、unordered_mapの定数倍が重いらしくsystestでtleした。つらい。

C. Running Track

問題

文字列$s,t$($|s|,|t| \le 2100$)が与えられる。$s$の部分文字列あるいはそれを反転させた文字列を連結して$t$を構成したい。その方法を答えよ。

解法

trie木。区間を広げながら木を潜れば$O(n^2)$となる。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
const int INF = 1000000006;
struct substr_t { int l, r; };
struct link_t { int l; int next; substr_t substr; };
struct trie_t { trie_t *p[26]; substr_t substr; };
trie_t *new_trie(int l, int r) {
    trie_t *t = new trie_t;
    memset(t->p, 0, sizeof(t->p));
    t->substr = { l, r };
    return t;
}
int main() {
    // input
    string s, t; cin >> s >> t;
    int sl = s.size();
    int tl = t.size();
    // construct trie
    trie_t root = {};
    repeat (l,sl) {
        trie_t *it = &root;
        repeat_from (r,l+1,sl+1) {
            int i = s[r-1]-'a';
            if (not it->p[i]) it->p[i] = new_trie(r,l+1); // reversed
            it = it->p[i];
        }
    }
    repeat (r,sl+1) {
        trie_t *it = &root;
        repeat_reverse (l,r) {
            int i = s[l]-'a';
            if (not it->p[i]) it->p[i] = new_trie(l+1,r); // reversed
            it = it->p[i];
        }
    }
    // run dp
    vector<link_t> dp(tl+1, (link_t){ INF });
    dp[0].l = 0;
    repeat (r,tl+1) {
        trie_t *it = &root;
        repeat_reverse (l,r) { // reversed
            int i = t[l]-'a';
            if (not it->p[i]) break;
            it = it->p[i];
            if (dp[l].l+1 < dp[r].l) {
                dp[r] = { dp[l].l+1, l, it->substr };
            }
        }
    }
    // output
    if (dp[tl].l == INF) {
        cout << -1 << endl;
    } else {
        cout << dp[tl].l << endl;
        link_t it = dp[tl];
        vector<link_t> lnks;
        while (it.l) {
            lnks.push_back(it);
            it = dp[it.next];
        }
        reverse(lnks.begin(), lnks.end());
        for (link_t lnk : lnks) {
            cout << lnk.substr.l << ' ' << lnk.substr.r << endl;
        }
    }
    return 0;
}