## C. Running Track

### 解法

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