#include <cstdio> #include <vector> using namespace std; vector<int>v; vector<int>pom; int p[1000111]; int n, m, a, b, t[1011][1011], zlicz; int main() { scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) { scanf("%d", &a); for(int j=1; j<=a; j++)scanf("%d", &t[i][j]); } v.push_back(0); for(int i=1; i<=m; i++) { scanf("%d", &a); v.push_back(a); } v.push_back(0); v.push_back(1); if(m==1&&v[1]==1) { printf("1"); return 0; } int i=2; while(v.size()<1000111) { int j=v.size()-1; while(j>m+1) { pom.push_back(v.back()); v.pop_back(); j--; } while(!pom.empty()) { for(int k=1; t[pom.back()][k]!=0; k++) { v.push_back(t[pom.back()][k]); } pom.pop_back(); } p[1]=0; zlicz=0; if(v.size()>1000000)break; for(int k=2; k<=v.size(); k++) { while(zlicz>0&&v[zlicz+1]!=v[k])zlicz=p[zlicz]; if(v[zlicz+1]==v[k])zlicz++; p[k]=zlicz; if(p[k]==m) { printf("%d", i); return 0; } } i++; } printf("-1"); getchar(); getchar(); 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 | #include <cstdio> #include <vector> using namespace std; vector<int>v; vector<int>pom; int p[1000111]; int n, m, a, b, t[1011][1011], zlicz; int main() { scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) { scanf("%d", &a); for(int j=1; j<=a; j++)scanf("%d", &t[i][j]); } v.push_back(0); for(int i=1; i<=m; i++) { scanf("%d", &a); v.push_back(a); } v.push_back(0); v.push_back(1); if(m==1&&v[1]==1) { printf("1"); return 0; } int i=2; while(v.size()<1000111) { int j=v.size()-1; while(j>m+1) { pom.push_back(v.back()); v.pop_back(); j--; } while(!pom.empty()) { for(int k=1; t[pom.back()][k]!=0; k++) { v.push_back(t[pom.back()][k]); } pom.pop_back(); } p[1]=0; zlicz=0; if(v.size()>1000000)break; for(int k=2; k<=v.size(); k++) { while(zlicz>0&&v[zlicz+1]!=v[k])zlicz=p[zlicz]; if(v[zlicz+1]==v[k])zlicz++; p[k]=zlicz; if(p[k]==m) { printf("%d", i); return 0; } } i++; } printf("-1"); getchar(); getchar(); return 0; } |