#include <iostream> #include <vector> //#include <cstdlib> //#include <conio.h> using namespace std; vector<int> teraz, nowy; vector<int> *a; int *wzor; int n, m, d; int * pref; bool ok(){ if(teraz.size()<m) return 0; else{ int t=0; int w=teraz.size(); for (int i = 0; i < w; i++) { while (t > 0 && teraz[i] != wzor[t] ) t=pref[t-1]; if(teraz[i] == wzor[t]) t++; if(t==m) return true; } } return false; } void wyznacz_p(){ pref[0] = 0; int t = pref[0]; for (int i = 1; i < m; i++) { while (t > 0 && wzor[i] != wzor[t] ) t=pref[t-1]; if(wzor[i] == wzor[t]) t++; pref[i] = t; //cout << pref[i]; } } void ewoluuj(){ vector<int>::iterator it, it2; nowy.clear(); for(it=teraz.begin(); it!= teraz.end(); it++){ for(it2=a[*it].begin(); it2!=a[*it]. end(); it2++){ nowy.push_back(*it2); } } teraz=nowy; } int main() { ios_base::sync_with_stdio(false); cin >> n >> m; a=new vector<int>[n]; wzor = new int[m]; int pom; int max=0; for(int i =0; i<n; ++i){ cin >> pom; if(pom>max)max=pom; a[i].resize(pom); for(int j=0; j<pom; j++){ cin >> d; a[i][j]=(d-1); } } for(int i=0; i<m; ++i){ cin >> wzor[i]; --wzor[i]; } pref=new int[m]; int j=0; int s=1; wyznacz_p(); teraz.push_back(0); while(j<4000000){ //cout << endl; // for(vector<int>::iterator it = teraz.begin(); it!=teraz.end(); it++) cout << *it << " "; // cout << endl << endl; if(ok()){ cout << s; return 0; } else ewoluuj(); s++; j+=(m+teraz.size()); if(teraz.size()*max+j>50000000) break; // getch(); } cout << -1; 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 | #include <iostream> #include <vector> //#include <cstdlib> //#include <conio.h> using namespace std; vector<int> teraz, nowy; vector<int> *a; int *wzor; int n, m, d; int * pref; bool ok(){ if(teraz.size()<m) return 0; else{ int t=0; int w=teraz.size(); for (int i = 0; i < w; i++) { while (t > 0 && teraz[i] != wzor[t] ) t=pref[t-1]; if(teraz[i] == wzor[t]) t++; if(t==m) return true; } } return false; } void wyznacz_p(){ pref[0] = 0; int t = pref[0]; for (int i = 1; i < m; i++) { while (t > 0 && wzor[i] != wzor[t] ) t=pref[t-1]; if(wzor[i] == wzor[t]) t++; pref[i] = t; //cout << pref[i]; } } void ewoluuj(){ vector<int>::iterator it, it2; nowy.clear(); for(it=teraz.begin(); it!= teraz.end(); it++){ for(it2=a[*it].begin(); it2!=a[*it]. end(); it2++){ nowy.push_back(*it2); } } teraz=nowy; } int main() { ios_base::sync_with_stdio(false); cin >> n >> m; a=new vector<int>[n]; wzor = new int[m]; int pom; int max=0; for(int i =0; i<n; ++i){ cin >> pom; if(pom>max)max=pom; a[i].resize(pom); for(int j=0; j<pom; j++){ cin >> d; a[i][j]=(d-1); } } for(int i=0; i<m; ++i){ cin >> wzor[i]; --wzor[i]; } pref=new int[m]; int j=0; int s=1; wyznacz_p(); teraz.push_back(0); while(j<4000000){ //cout << endl; // for(vector<int>::iterator it = teraz.begin(); it!=teraz.end(); it++) cout << *it << " "; // cout << endl << endl; if(ok()){ cout << s; return 0; } else ewoluuj(); s++; j+=(m+teraz.size()); if(teraz.size()*max+j>50000000) break; // getch(); } cout << -1; return 0; } |