#include <bits/stdc++.h> using namespace std; const int MAXN = 500; const int MAXM = 1000; const int LIMIT = 9000000; int n, m, a, b; vector <int> R[MAXN + 5]; vector <int> pattern; vector <int> seq; int p[MAXM + 5]; int cnt; bool is_pattern_present(); void knuth(); void replace(); int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i) { scanf("%d", &a); for(int j = 0; j < a; ++j) { scanf("%d", &b); R[i].push_back(b); } } for(int i = 0; i < m; ++i) { scanf("%d", &a); pattern.push_back(a); } knuth(); cnt = 1; seq.push_back(1); while(!is_pattern_present()) { if(seq.size() > LIMIT) { printf("-1\n"); return 0; } ++cnt; replace(); } printf("%d\n", cnt); return 0; } bool is_pattern_present() { int act = 0; for(int i = 0; i < seq.size(); ++i) { while(act > 0 && seq[i] != pattern[act]) act = p[act - 1]; if(seq[i] == pattern[act]) ++act; if(act == pattern.size()) return true; } return false; } void replace() { vector <int> tmp; for(int i = 0; i < seq.size(); ++i) { for(int j = 0; j < R[seq[i]].size(); ++j) { tmp.push_back(R[seq[i]][j]); } } seq = tmp; } void knuth() { int act = 0; for(int i = 1; i < pattern.size(); ++i) { while(act > 0 && pattern[i] != pattern[act]) act = p[act - 1]; if(pattern[i] == pattern[act]) ++act; p[i] = act; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include <bits/stdc++.h> using namespace std; const int MAXN = 500; const int MAXM = 1000; const int LIMIT = 9000000; int n, m, a, b; vector <int> R[MAXN + 5]; vector <int> pattern; vector <int> seq; int p[MAXM + 5]; int cnt; bool is_pattern_present(); void knuth(); void replace(); int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i) { scanf("%d", &a); for(int j = 0; j < a; ++j) { scanf("%d", &b); R[i].push_back(b); } } for(int i = 0; i < m; ++i) { scanf("%d", &a); pattern.push_back(a); } knuth(); cnt = 1; seq.push_back(1); while(!is_pattern_present()) { if(seq.size() > LIMIT) { printf("-1\n"); return 0; } ++cnt; replace(); } printf("%d\n", cnt); return 0; } bool is_pattern_present() { int act = 0; for(int i = 0; i < seq.size(); ++i) { while(act > 0 && seq[i] != pattern[act]) act = p[act - 1]; if(seq[i] == pattern[act]) ++act; if(act == pattern.size()) return true; } return false; } void replace() { vector <int> tmp; for(int i = 0; i < seq.size(); ++i) { for(int j = 0; j < R[seq[i]].size(); ++j) { tmp.push_back(R[seq[i]][j]); } } seq = tmp; } void knuth() { int act = 0; for(int i = 1; i < pattern.size(); ++i) { while(act > 0 && pattern[i] != pattern[act]) act = p[act - 1]; if(pattern[i] == pattern[act]) ++act; p[i] = act; } } |