Submission #51064224

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define fio ios::sync_with_stdio(0);cin.tie(0)
#define For(i,n) for (int i=1;i<=(int)(n);i++)
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define all(x) (x).begin(),(x).end()
#define clr(i) memset(i,0,sizeof(i))
#define Max(a,b,c) max(a,max(b,c))
#define Min(a,b,c) min(a,min(b,c))
#define fore(i,x) for (auto &i:x)
#define pii pair <int,int>
#define vi vector <int>
#define pb push_back
#define ll long long
#define endl '\n'
#define re return
#define se second
#define fi first

const int INF = 0x7ffffff;
const int MAXN = +3;

vector <string> v[103];

int f[103];

int main() {
	For(i, 100) f[i] = INF;
	string S;
	int n;
	cin >> S >> n;
	rep(i, n) {
		int x;
		cin >> x;
		v[i].resize(x);
		fore(j, v[i]) cin >> j;
	}
	rep(t, n) {
		for (int i = S.size() - 1;i >= 0;i--) {
			fore(s, v[t]) {
				if (i - int(s.size()) + 1 >= 0) {
					string ts = S.substr(i - int(s.size()) + 1, s.size());
					if (ts == s) {
						f[i + 1] = min(f[i + 1], f[i - s.size() + 1] + 1);
					}
				}
			}
		}
	}
	if (f[S.size()] == INF) {
		cout << -1 << endl;
	} else {
		cout << f[S.size()] << endl;
	}
	return 0;
}

Submission Info

Judge Result