解法
DP. 状態を，\(T\) の \([0,j)\) まで一致させたとして \(j\) をもつ． \(S_{i}\) を使えるかどうかは， \(T_{[0,j)} + S_{i} = T_{[0,j+|S_{i}|)}\) と同値．
注意
substr は，範囲外にならない様に．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
string t; cin >> t;
ll n; cin >> n;
rep(i,n){
ll a; cin >> a;
s[i].resize(a);
cinv(s[i]);
}
// O(n * t.size() * sum_{i \in n and str \in s[i]} |str|)
ll inf = n+1;
vll dp(t.size()+1, inf);
dp[0] = 0;
int main() {
string t; cin >> t;
ll n; cin >> n;
rep(i,n){
ll a; cin >> a;
s[i].resize(a);
cinv(s[i]);
}
// O(n * t.size() * sum_{i \in n and str \in s[i]} |str|)
ll inf = n+1;
vll dp(t.size()+1, inf);
dp[0] = 0;
rep(i,n) {
drep(ti, t.size()+1) {
for(auto str: s[i]){
if(t.substr(ti, str.length()) == str){
chmin(dp[ti + str.length()], dp[ti] + 1);
}
}
}
}
ll ans = dp[t.size()];
if(ans >= inf) ans = -1;
cout << ans << endl;
return 0;
}
drep(ti, t.size()+1) {
for(auto str: s[i]){
if(t.substr(ti, str.length()) == str){
chmin(dp[ti + str.length()], dp[ti] + 1);
}
}
}
}
ll ans = dp[t.size()];
if(ans >= inf) ans = -1;
cout << ans << endl;
return 0;
}
