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;
}