#include <iostream> #include <vector> using namespace std; vector<int> P(1001); int m; // size of P vector<int> b(1001); void kmpPreprocess() { int i = 0, j = -1; b[0] = -1; while (i < m) { while (j >= 0 && P[i] != P[j]) j = b[j]; i++; j++; b[i] = j; } } bool kmpSearchShort(vector<int> T, int sz) { // this is similar as kmpPreprocess(), but on string T int i = 0, j = 0; // starting values while (i < sz) { // search through string T while (j >= 0 && T[i] != P[j]) { j = b[j]; // if different, reset j using b } i++; j++; // if same, advance both pointers if (j == m) { // a match found when j == m // cout << "match at " << i - j << " where sz " << sz << " and m " << m << endl; // for (int q = i - j; q < i; ++q) { // cout << "T[q] " << T[q] << " P[q] " << P[q] << endl; // } return true; // j = b[j]; // prepare j for the next possible match } } return false; } #define MAXIT 20000 #define MAXLEN 500000000 int main() { int n; cin >> n; cin >> m; vector<vector<int> > pats(n+1); for (int i = 0; i < n; ++i) { int patsize; int x; cin >> patsize; for (int j = 0; j < patsize; ++j) { cin >> x; pats[i+1].push_back(x); } } for (int i = 0; i < m; ++i) { int x; cin >> x; P[i] = x; } vector<int> kom[2]; kom[0].push_back(1); kmpPreprocess(); for (int y = 1; y < MAXIT; ++y) { int nu = y % 2; int ol = 1 - nu; // cout << "kom generation " << y << "| "; // for (int z = 0; z < kom[ol].size(); ++z) { // cout << kom[ol][z] << " | "; // } // cout << endl; kom[nu].clear(); int cnt = kom[ol].size(); if (cnt > MAXLEN) { // cout << "maxlen!" << endl; cout << "-1" << endl; return 0; } for (int i = 0; i < kom[ol].size(); ++i) { cnt += kom[ol].size(); if (cnt > MAXLEN) { // cout << "maxlen!!" << endl; cout << "-1" << endl; return 0; } int sel = kom[ol][i]; for (int j = 0; j < pats[sel].size(); ++j) { kom[nu].push_back(pats[sel][j]); } } if ((kom[nu].size() >= m) && (kmpSearchShort(kom[nu], kom[nu].size()) == true)) { cout << y + 1 << endl; return 0; } } cout << "-1" << endl; 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 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #include <iostream> #include <vector> using namespace std; vector<int> P(1001); int m; // size of P vector<int> b(1001); void kmpPreprocess() { int i = 0, j = -1; b[0] = -1; while (i < m) { while (j >= 0 && P[i] != P[j]) j = b[j]; i++; j++; b[i] = j; } } bool kmpSearchShort(vector<int> T, int sz) { // this is similar as kmpPreprocess(), but on string T int i = 0, j = 0; // starting values while (i < sz) { // search through string T while (j >= 0 && T[i] != P[j]) { j = b[j]; // if different, reset j using b } i++; j++; // if same, advance both pointers if (j == m) { // a match found when j == m // cout << "match at " << i - j << " where sz " << sz << " and m " << m << endl; // for (int q = i - j; q < i; ++q) { // cout << "T[q] " << T[q] << " P[q] " << P[q] << endl; // } return true; // j = b[j]; // prepare j for the next possible match } } return false; } #define MAXIT 20000 #define MAXLEN 500000000 int main() { int n; cin >> n; cin >> m; vector<vector<int> > pats(n+1); for (int i = 0; i < n; ++i) { int patsize; int x; cin >> patsize; for (int j = 0; j < patsize; ++j) { cin >> x; pats[i+1].push_back(x); } } for (int i = 0; i < m; ++i) { int x; cin >> x; P[i] = x; } vector<int> kom[2]; kom[0].push_back(1); kmpPreprocess(); for (int y = 1; y < MAXIT; ++y) { int nu = y % 2; int ol = 1 - nu; // cout << "kom generation " << y << "| "; // for (int z = 0; z < kom[ol].size(); ++z) { // cout << kom[ol][z] << " | "; // } // cout << endl; kom[nu].clear(); int cnt = kom[ol].size(); if (cnt > MAXLEN) { // cout << "maxlen!" << endl; cout << "-1" << endl; return 0; } for (int i = 0; i < kom[ol].size(); ++i) { cnt += kom[ol].size(); if (cnt > MAXLEN) { // cout << "maxlen!!" << endl; cout << "-1" << endl; return 0; } int sel = kom[ol][i]; for (int j = 0; j < pats[sel].size(); ++j) { kom[nu].push_back(pats[sel][j]); } } if ((kom[nu].size() >= m) && (kmpSearchShort(kom[nu], kom[nu].size()) == true)) { cout << y + 1 << endl; return 0; } } cout << "-1" << endl; return 0; } |