//brute #include <cstdio> #include <vector> using std::printf; using std::scanf; using std::vector; int n, m; vector<int> transforms[501]; vector<int> sequence; vector<int> bajtokomorczak; vector<int> nowyBajtokomorczak; int prefixes[1001]; void preKMP() { prefixes[0] = -1; for (int i = 0; i < sequence.size(); i++) { prefixes[i + 1] = prefixes[i] + 1; while (prefixes[i + 1] > 0 && sequence[i] != sequence[prefixes[i + 1] - 1]) prefixes[i + 1] = prefixes[prefixes[i + 1] - 1] + 1; } } bool kmp() { for (int i = 0, j = 0; i < bajtokomorczak.size();) { if (j < 0 || bajtokomorczak[i] == sequence[j]) { ++i, ++j; if (j == sequence.size()) { return true; } } else j = prefixes[j]; } return false; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { int count; scanf("%d", &count); while (count--) { int next; scanf("%d", &next); transforms[i].push_back(next); } } for (int i = 0; i < m; i++) { int next; scanf("%d", &next); sequence.push_back(next); } preKMP(); bajtokomorczak.push_back(1); for (int i = 1; i < 1000; i++) { if (kmp()) { printf("%d\n", i); return 0; } nowyBajtokomorczak.clear(); for (vector<int>::iterator it = bajtokomorczak.begin(); it != bajtokomorczak.end(); it++) { for (vector<int>::iterator it2 = transforms[*it].begin(); it2 != transforms[*it].end(); it2++) nowyBajtokomorczak.push_back(*it2); } bajtokomorczak = nowyBajtokomorczak; } printf("-1\n"); return 0; }
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 75 76 77 78 79 80 81 82 83 | //brute #include <cstdio> #include <vector> using std::printf; using std::scanf; using std::vector; int n, m; vector<int> transforms[501]; vector<int> sequence; vector<int> bajtokomorczak; vector<int> nowyBajtokomorczak; int prefixes[1001]; void preKMP() { prefixes[0] = -1; for (int i = 0; i < sequence.size(); i++) { prefixes[i + 1] = prefixes[i] + 1; while (prefixes[i + 1] > 0 && sequence[i] != sequence[prefixes[i + 1] - 1]) prefixes[i + 1] = prefixes[prefixes[i + 1] - 1] + 1; } } bool kmp() { for (int i = 0, j = 0; i < bajtokomorczak.size();) { if (j < 0 || bajtokomorczak[i] == sequence[j]) { ++i, ++j; if (j == sequence.size()) { return true; } } else j = prefixes[j]; } return false; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { int count; scanf("%d", &count); while (count--) { int next; scanf("%d", &next); transforms[i].push_back(next); } } for (int i = 0; i < m; i++) { int next; scanf("%d", &next); sequence.push_back(next); } preKMP(); bajtokomorczak.push_back(1); for (int i = 1; i < 1000; i++) { if (kmp()) { printf("%d\n", i); return 0; } nowyBajtokomorczak.clear(); for (vector<int>::iterator it = bajtokomorczak.begin(); it != bajtokomorczak.end(); it++) { for (vector<int>::iterator it2 = transforms[*it].begin(); it2 != transforms[*it].end(); it2++) nowyBajtokomorczak.push_back(*it2); } bajtokomorczak = nowyBajtokomorczak; } printf("-1\n"); return 0; } |